[프로그래머스 Lv.2] 줄 서는 방법 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12936

프로그래머스

풀이

처음에 단순하게 문제를 생각했을 때, itertools의 permutation을 활용하여 순열을 모두 생성해 두고, 여기서 k번째에 해당하는 순열을 찾는 방식으로 해결하려 하였다. 하지만 n의 최댓값인 20의 경우를 생각하여 보면, 20!이라는 어마무시한 숫자이기에 이 방법으로는 해결이 불가능하였다.

 

그래서 약간은 수학적인 방법을 사용해보았다. n=3일 때의 간단한 예시를 들어보겠다.

[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]을 아래와 같이 나눠보겠다.

• [1, 2, 3], [1, 3, 2] / [2, 1, 3], [2, 3, 1] / [3, 1, 2], [3, 2, 1]

위와 같이 첫째 자리가 나눠지게 경계를 그어보게 되면 2개씩 나뉘게된다. 3개 중에서 첫째 자리를 결정하게 되면 나열해야 하는 나머지 숫자는 2개이기에 이때 경우의 수는 2!이다.

마찬가지로 n=4인 경우라면 첫째 자리를 결정하게 되면 나머지 숫자는 3개이기에, 경계가 3!=6개를 기준으로 나눠진다.

 

즉, n개의 숫자가 있을 때 첫번째 자리를 결정하는 방법은 (n-1)!로 나눈 몫을 사용하면 되는 것이다. 다만 여기서 주의해야 할 부분이 있다. 간단한 예시로 n=3, k=2일 때 첫번째 자리가 무엇일지 생각해 보자. 2!로 나눈 몫은 k/2! = 2/2 = 1이다. 몫이 0이 아니기에, 그럼 첫째 자리가 1인 경우는 앞서 다 지나왔다는 얘기가 되는데 실제로 k=2일 때 정답은 [1, 3, 2]로 아직 첫째 자리가 1이다. 이렇게 나눠 떨어지는 경우에 앞서 가정했던 내용과 간극이 발생하게 되는데, 이를 방지하기 위해 우리는 k값을 1을 빼주고 구현을 시작하면 된다.

 

결론적으로 n개의 숫자를 나열할 때 k번째의 순열을 찾으려면 (n-1)!마다 첫째 자리가 바뀌는 점을 고려하여, (k-1)을 (n-1)!로 나눈 몫을 앞자리를 결정할 때 사용하고 (몫이 0이면 남은 숫자 중에 첫 번째 숫자, 1이면 두 번째 숫자와 같이), 나머지는 다시 다음 자리를 결정하는 데 사용하게 하면 k번째의 순열을 찾을 수 있다.

from math import factorial

def solution(n, k):
    answer = []
    numbers = [i for i in range(1, n+1)] # 순열을 이루는데 사용될 숫자를 모아놓은 배열
    k -= 1 # k-1을 해야 나누어 떨어지는 경우에 대한 처리가 올바르게 이뤄질 수 있음

    while n > 0: # n개의 숫자를 모두 사용할 때까지 반복
        d, k = divmod(k, factorial(n-1)) # 몫은 첫째 자리를 결정하는데 사용, 나머지는 다시 다음 숫자를 결정하는데 사용
        n -= 1
        answer.append(numbers.pop(d)) # 남은 숫자에서 d번째 존재하는 숫자가 (d번째로 작은 숫자) 다음에 순열에 나타날 숫자임
    
    return answer