[프로그래머스] 줄 서는 방법 (파이썬)

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

🔎n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다.
예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항
- n은 20이하의 자연수 입니다.
- k는 n! 이하의 자연수 입니다.

---

정답에 대한 접근은 옳게 했으나, 멍청하게 구현하는 바람에 많은 시간을 허비해버렸다.

 

기본적으로 순열에 대한 이해가 있으면 어렵지 않게 풀 수 있는 문제인 것 같다.

 

<정답 코드>

def solution(n, k):
    people = [i for i in range(1, n+1)]
    answer = []
    facto = [1, 1]
    
    for i in range(2, n+1):
        facto.append(facto[i-1]*i)
        
    k -= 1
    
    while n:
        tmp = facto[n-1]
        answer.append(people[k//tmp])
        people.pop(k//tmp)
        k, n = k%tmp, n-1

    return answer

 

접근은 팩토리얼 계산을 위한 DP와 순열의 계산식을 이용했다.

 

n명의 서로 다른 사람들을 배치하는 방법은 n!가지 방법이 있다. 5명의 사람들을 배치한다고 가정해보자.

 

그러면 순열 계산식에 따라 5! = 120가지의 배치 방법이 있다. 번호가 작은 순으로 배치 순서를 매긴다고 하면, 아래 배치 방법이 첫번째 방법이 된다.

여기서 가장 첫번째 오는 사람으로 1번을 고정해놓는다면, 

이와 같이 나타난다. 

그 개수를 구해보면, 1을 제외한 나머지를 먼저 배치한 후 앞에 1을 배치하는 방법과 같으므로 (5-1)! = 24가지 방법이 있다.

 

이 원리로 2번이 가장 앞에 오게되는 배치들 중 가장 첫번째 순서는 1번이 가장 앞에오는 경우의 수 +1이 된다. 즉, 25번째 배치 방법부터 2번이 가장 앞에 오게 된다. 

 

그렇다면 k가 25보다 작으면 1번이 반드시 가장 처음에 나타나야 한다. 3번이 가장 앞에 오는 경우도 마찬가지다. 3번이 가장 앞에 나타나는 순서는 2 * (5-1)! + 1 = 49, 즉 k가 49이상이어야 3번이 가장 앞에 올 수 있고, 49보다 작은 경우 2번 또는 1번이 가장 앞에 온다.

 

이 원리를 모든 자리에 적용한다.

k를 통해 가장 먼저 등장할 번호를 구한다. k를 (n-1)!로 나눈 몫이 그 번호가 될 것이다. 해당 번호 사람을 answer배열에 세워둔 후, 그를 뺀 나머지 사람들에서 다음 차례에 올 사람을 구해야 하므로, 사람 배열에서 해당 번호 사람을 pop해준다.

그리고 k를 k % (n-1)!로, n을 n-1로 업데이트 해주면서 n이 0이 될 때 까지 반복하면 정답이 된다.

 

(k-1을 해주고 반복문을 시작한다. 이것은 우리가 리스트를 살필 때 첫번째 인덱스가 1이 아닌 0인 원리와 같다.)

 

원리가 그렇게 어렵진 않았지만, 해당 번호 사람을 제거할 때 pop을 사용하지 않고 굳이 set을 이용해 구현해보겠다는 무모한 도전 때문에 한두번 실패했었다.