프로그래머스: 줄 서는 방법

문제

코딩테스트 연습 - 줄 서는 방법

 

문제 풀이

 처음 문제를 접하였을 때는 `DFS`를 통해 각 경우의 수를 구하고 `K`인 경우를 반환하면 되지 않을까 생각했다. 하지만 이 방식은 `N`이 20이므로 시간 초과가 발생한다. 따라서 `K`인 경우를 바로 구할 수 있는 방법을 통해 풀어야 시간 초과가 발생하지 않는다. 즉, 이 문제는 단순히 `DFS`를 통해 조합을 구할 수 있는가?를 묻는 문제가 아닌 팩토리얼 성질을 통해 효율적으로 K인 경우의 조합을 찾을 수 있는가?를 묻는 문제이다.

 

 예를 들어 N이 3인 경우, 경우의 수는 다음과 같이 나열할 수 있다.

• `[1, 2, 3]`, `[1, 3, 2]`
• `[2, 1, 3]`, `[2, 3, 1]`
• `[3, 1, 2]`, `[3, 2, 1]`

 즉, 앞자리 수에 따라 2가지 경우가 발생한다는 것을 알 수 있다. 따라서 첫 번째에 올 수 있는 경우의 수는 `(N - 1)!`과 같다. 이와 같은 성질을 이용하여 `K`를 `(N - 1)!`로 나누면 첫 번째 자리에 어떤 숫자가 오는지 찾을 수 있다. 이를 통해 `DFS`와 달리 `K`인 경우에 각 자릿수를 찾을 수 있다.

 

코드

from math import factorial


def solution(n, k):
    answer = []
    nums = list(range(1, n + 1))

    while n != 0:
        f = factorial(n - 1)
        answer.append(nums.pop((k - 1) // f))
        n -= 1
        k %= f

    return answer