[Python] 줄 서는 방법

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

풀이

1. 제한사항에서 n은 20이하의 자연수라고 되어있다. 시간 복잡도가 n! 인 permutations를 사용하면 제한시간 초과로 풀지 못하는 테스트 케이스가 발생한다.

2. 수학적 응용과 문제의 규칙을 이용해서 풀어야함.

3. 문제에서 처럼 k를 5라고 했을때, k 이전에 있는 배열의 개수는 4. 이 중에 1로 시작하는 경우 2개, 2로 시작하는 경우 2개이다.

즉, n = 3일때, 하나를 골랐을 때 나머지를 고를 수 있는 경우의 수와 같다. 이는 2! 개이며 (n-1)개이다. (순열 경우의 수 참조)

4. 이 k를 fact(n-1)로 나눈 몫을 인덱스로, 나머지를 다음 순서로 둔다.

 

from math import factorial

def sol(n,k):
	answer = []
    people = [i for i in range(1, n+1)]
    
    while != 0:
    	fact = factorial(n-1)
        answer.append(people.pop((k-1) // fact))
        n -= 1
        k %= fact
   
    return answer