[Python] 프로그래머스. 줄 서는 방법 (Level 3)

programmers.co.kr/learn/courses/30/lessons/12936

코딩테스트 연습 - 줄 서는 방법

수학응용이 약간 필요한 문제. 모든 경우의 수를 조사하는 permutations를 쓰면 시간초과가 난다. n이 20 이하이므로 최대 2.4 * 10^18 의 개수가 나오는데, 이걸 permutations로 리스트 변환하는 것이 불가능하기 때문.

 

사전순 배열에서 k번째 위치 값만 리턴하면 되므로, k번째 값에 근접하도록 '생성할 수 있는 경우의 수'로 나누면 된다.

 

[1,2,3] 예시의 경우

맨 앞자리가 1일 경우, 생성할 수 있는 개수는 2! = 2가 된다. 즉 [1,2,3], [1,3,2] 두 개.

즉 맨 앞에서부터 첫 번째와 두 번째는 맨 앞자리가 무조건 1이다.

그렇다면 세 번째부터는 무조건 맨 앞자리가 2이고, 다섯 번째부터는 맨 앞자리가 무조건 3이 된다.

 

k가 5라면,

앞자리 1인 경우가 2개 + 앞자리 2인 경우가 2이므로 네 개의 숫자를 건너뛰어야 한다. 따라서 k번째 숫자의 맨 앞자리는 3이 된다.

이 규칙을 활용하면 된다.