문제 풀이 방식
<처음 풀이 방식>
from itertools import permutations
def solution(n, k):
firstLine = list(range(1, n + 1))
lines = list(permutations(firstLine, len(firstLine)))[k - 1:k]
return lines.pop()
< factorial 풀이방식 >
" 순열의 순원리도 factorial과 같음 "
n명을 줄 세우는 방법의 수는 n!
첫번째 자리가 정해진 후 나머지의 줄 서는 방식의 수는 n-1!가지
만약 [1,2,3]일 경우
첫번째 자리 정해져 있을 경우 : nP1 * (n-1)!
1번이 첫번째 자리일 경우 2(n-1!)가지
2번이 첫번째 자리일 경우도 2(n-1!)가지
3번이 첫번째 자리일 경우도 2(n-1!)가지
두번째 자리까지 정해져 있을 경우 : nP2 * (n-2)!
k-1 // factorial 로 나눈 이유
: line에서 해당 인덱스를 찾아 pop 하기 위함
k-1은 직관적으로는 k번째이지만 인덱스로 따지면 k-1번째이기 때문에
구체적으로 설명
line = [1,2,3]
K-1번째 : 앞자리
0번째 ~ : 1
2번째 ~ : 2
4번째 ~ : 3
(k-1) // (n-1)! = line의 인덱스 ( 찾고자 하는 사람번호 )
line2 = [1,2,3,4]
i+(n-1)!=k번째 : 앞자리
1번째 ~ : 1
7번째 ~ : 2
13번째 ~ : 3
19번째 ~ : 4
(k-1) // (n-1)! = "line의 인덱스"
(k-1) = 0,1,2,3,4,5까지는 "line의 인덱스"가 1
(k-1) = 6,7,8,9,10,11까지는 "line의 인덱스"가 2
(k-1) = 12,13,14,15,16,17까지는 "line의 인덱스"가 3
(k-1) = 18,19,20,21,22,23까지는 "line의 인덱스"가 4
k %= factorial 한 이유
: k를 차례대로 줄이는 과정
즉, 구현은 permutations을 쓰면 되지만 시간초과로 순열의 순원리인 factorial을 이용하여 원하는 부분만 출력해야함