통과 못한 내 풀이
from itertools import permutations
def solution(n, k):
people = [i for i in range(1, n+1)]
answer = list(permutations(people, n))
return list(answer[k-1])시간초과가 난다. 20!이다.
다른 사람 풀이
import math
def solution(n, k):
answer = [num for num in range(1,n+1)]
answer_list = []
while n > 0 :
n -= 1
share, remainder = divmod(k,math.factorial(n))
if not remainder: share -= 1
answer_list.append(answer[share])
answer.remove(answer[share])
k = remainder
return answer_listn명을 총 줄세우는 방법은 n!입니다. 예를 들어서 위와 같은 3명을 줄을 세우면 3!가지가 전체 줄을 서는 경우의 수입니다. 잘 살펴보면, 각 사람들이 첫 번째에 있을 경우 2가지입니다.(1번 사람이 첫 번째에 있을 경우 2가지, 2번 사람이 첫 번째에 있을 경우 2가지, 3번 사람이 첫 번째에 있을 경우 2가지) 이를 수식으로 살펴보면 각 사람이 첫 번째에 올 경우의 수는 (n-1)!과 같습니다. 이것을 이용하여 한자리씩 구해나가면 됩니다! 따라서 k를 (n-1)!로 나누면, k번째 방법에 어떤 수가 가장 앞에 있는지 알 수 있습니다. 나눈 몫은 숫자를 구하는데 사용하고, 나머지는 반복문을 통해 다음 숫자를 찾는데 사용합니다. 다음 수는 remainder 나누기 ((n-1)-1)!를 하시면 됩니다! 이렇게 마지막 자리수까지 계속 반복하시면 됩니다!
