CodeDrive

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 함수를 완성해주세요.

1번부터 n명까지 줄을 서는 총 경우의 수를 보면 맨 앞에 서 있는 사람이 m번인 경우는 보통 (n-1)!개씩 있다.

왜냐하면 1번부터 n명까지 줄을 서는 총 경우의 수는 n!개 일 때, 맨 앞의 수를 임의의 m으로 잡고 난 뒤 나머지 수들을 배열하는 방법은 (n-1)! 이기 때문이다.

따라서 k를 (n-1)!으로 나눈다면 k번째 방법이 어떤 임의의 수 m번이 맨 앞으로 오는지 알 수 있게 된다. 맨 앞의 수를 정한 뒤 그 뒤에 올 수들도 앞의 방법가 동일하게 정해주면 사전순으로 나열이 될 것이다. k를 (n-1)!으로 나누고 몫은 맨 앞의 수를 정하는데 사용하고 나머지는 다시 한번 ((n-1)-1)!으로 나누어서 다음 수를 정해주는 방식으로 진행 하면 된다.