https://school.programmers.co.kr/learn/courses/30/lessons/12936
import math
def solution(n, k):
answer = []
num_list = [i for i in range(1, n+1)] # 사람들
while (n != 0):
temp = math.factorial(n) // n # 맨 앞자리를 제외한 나머지 자리들의 경우의 수
index = k // temp # temp가 몇 번 지나갔는지
k = k % temp # temp만큼 지나가고 나머지
if k == 0: # 나누어 떨어져서 index - 1을 answer에 추가
answer.append(num_list.pop(index-1))
else:
answer.append(num_list.pop(index))
n -= 1
return answer
print(solution(3, 5))
ex) n = 3, k = 5
temp = math.factorial(n) // n
를 하면 6 // 3
으로 2가 된다.
-> [1,2,3][1,3,2] [2,1,3][2,3,1] [3,1,2][3,2,1]로 각 숫자당 2개의 방법이 생긴다.
index = k // temp
를 하면 5 // 2
, k = k % temp
를 하면 5 % 2 = 1
이 된다.
-> 2번 지나가고 1이 남은 것이다. [1,2,3][1,3,2] [2,1,3][2,3,1] 지나가고 [3,1,2]이 남은 것
-> 3을 추가하기 위해 num_list[index]을 추가한다.
k % temp
가 0이면 나누어 떨어진 것이므로 num_list[index - 1]를 추가한다.
이제 이걸 반복해주면 된다. n이 1 줄어들면 2가 되고, temp = 2 // 2가 되어 1이 된다. index = 1 // 1 이라 1이 된다. k = 1이 된다. 이제 answer에 index -1 즉 0번째를 넣어주면 1이 들어간다. n - 1 을 하면 n 은 1 이된다.
마지막으로 temp = 1, index = 1 // 1이므로 1이 되고 k = 1 %1이라 0이되어 첫번째 원소를 넣어주면 [3, 1, 2]가 된다.