[프로그래머스] Lv2. 줄 서는 방법

lemythe423·2023년 7월 19일

풀이

❌ n = 20, k = 20! 이기 때문에 완전탐색으로는 불가능

⭕️ 순열 + 팩토리얼

n = 4라고 했을 때, 첫 번째 자리의 숫자가 1이 되는 방법은 총 3 x 2 x 1 이다. 첫 번째 자리의 숫자가 정해졌으므로 나머지 자리는 총 3자리가 되고 남은 숫자는 [2, 3, 4]로 총 3가지이다. 각각의 자리에 임의의 숫자를 하나씩 넣으면서 계산하면 두 번째 자리에는 3가지의 숫자가 올 수 있고, 세 번째 자리에는 2자리, 마지막에 올 수 있는 숫자는 하나만 남기 때문.

첫 번째 자리부터 n번째 자리까지 각각의 자리에 어떤 숫자를 넣어야 k를 넘지 않을 수 있는지 계산하면서 k번째에 접근해나가는 방식으로 풀었다. 각 자리의 숫자가 정해졌을 때 몇 가지의 방법을 가질 수 있느냐의 여부는 팩토리얼로 구할 수 있다.

order 라는 배열은 단순히 1부터 n까지의 정수를 담고 있는 배열로, n = 3인 경우 [1, 2, 3]이 된다. k = 5이고, 첫 번째 자리의 숫자가 정해졌을 때 가질 수 있는 방법의 수는 factorial[2] = 2 * 1 = 2가 된다.

계산을 편하게 하기 위해서 k -= 1을 하고 시작한다. k = 4가 되고 2로 나누게 되면 몫은 2, 나머지는 0이다. 몫이 2라는 것은 order에서 현재 2번째 인덱스에 있는 값이 첫 번째 숫자로 올 수 있다는 뜻이다. 첫 번째 숫자가 1일 때 2가지, 2일 때 2가지를 가질 수 있는데 그렇게 가질 수 있는 4라는 숫자보다도 k(=5)가 큰 숫자이기 때문이다. 첫 번째 자리의 숫자는 1,2 보다 커야 하므로 3이 된다.

이제 order = [1, 2]가 되고 k = 0 이 된다. k = 0 이라는 건 현재 숫자가 정답이라는 뜻인데 아직 answer = [3]이므로, 남아있는 숫자들이 정렬되어 있는 배열 order를 이 뒤에 붙이면 바로 정답을 구할 수 있다. answer + order = [3, 1, 2]가 정답.

def solution(n, k):
    answer = []
    order = [x for x in range(1, n+1)]
    
    # 팩토리얼 배열을 만들어서 미리 구해놓기
    factorial = [0]*(n-1)
    factorial[0] = 1
    
    for i in range(1, n-1):
        factorial[i] = factorial[i-1] * (i+1)
    
    k -= 1
    for factor in factorial[::-1]:
        answer.append(order.pop(k//factor))
        k %= factor
        if k == 0:
            return answer + order
        
    return answer