먼저 단순히 순열로 모든 조합을 다 찾고 그 중 k번째 수를 찾는 것은 n이 최대 20이기 때문에 총 의 경우의 수가 발생해 효율성 테스트를 통과하지 못한다.
이를 해결하고자 backtracking으로 가지치기를 해보았지만 이 역시 효율성 테스트를 통과하지 못했다.
다시 문제를 읽어보니 수학적 사고력을 요하는 문제라는 것을 알 수 있었다. 힌트는 "사람을 나열 하는 방법을 사전 순으로 나열 했을 때" 란 말이었다.
사전 순으로 나열했기 때문에 의 몫은 배열의 index가 된다. 이 때 가 아니라 을 하는 이유는 배열의 index값이 0부터 시작하는 것에 맞추기 위한 기믹이다.
몫이 정해지면 값을 위 식에서 나온 나머지로 갱신해 이 0이 될때까지 반복해주면 답을 구할 수 있다.
예를 들어, 이라 하면 몫은 가 되고 answer배열의 첫번째 자리수는 배열의 2번째 index에 해당하는 값 3으로 정해진다. 값이 정해지면 3을 기존 배열에서 제거하여 로 만들고 값을 나머지인 으로 갱신하고 이 과정을 반복한다.
def solution(n:int, k: int) -> list:
"""[summary]
Args:
n (int): the number of all people
k (int): kth case
Returns:
list: [description]
"""
answer = [0] * n
c = [x for x in range(1, n+1)]
def factorial(N):
res = 1
for i in range(1, N+1):
res *= i
return res
answer_idx = 0
k -= 1
while n > 0:
num = factorial(n-1)
idx = k // num
k = k % num
answer[answer_idx] = c.pop(idx)
answer_idx += 1
n -= 1
return answer