[프로그래머스] lv2 줄 서는 방법_python

이번 문제는 줄 서는 방법.
3명이 줄을 서는 방법은 3!, 총 6가지이다. 물론 배치는 사전순.
이 문제 lv2라 얕보고 고생했다.

우선 손으로 풀어보면 3명이 줄서는 방법은 아래와 같다.
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
여기서, 5번째 순서를 도출해야한다.
보면 앞자리에 특정숫자는 (n-1)!의 갯수를 가진다. 무슨 소리냐면
1이 앞에 오는 배열은 2개 즉 (3-1)! 개 이다. 처음엔 이게 맞는가 했는데 직접 해보니 맞다.

그렇다면 우리가 구해야하는건 5번째, (k-1)/(n-1)! 해주면 해당 index가 나온다.
index에 맞는 숫자를 꺼내 answer에 추가한다.
그 뒤 숫자배열은 또 (n-1)!이 된다. 즉 n이 0이 될때까지 반복.
k는 매번 업데이트 해야한다. 위 문제를 예로 들면 처음엔 5번째에 오는 첫숫자를 구하기였다.
2번째 숫자를 구하기 위해 k%(n-1)! 하여 첫자리가 구해진 후 다음 올 숫자를 구한다. 
즉, 첫자리가 3인 숫자 배열중 첫번째 오는 배열이 답이 될것이다.
그렇게 쌓아주면 답이 나온다.

import math

def solution(n, k):
    answer = []
    # 1에서 n까지의 숫자를 담아두기
    num_lst = [i for i in range(1, n+1)]
    
    while n != 0:
    	# 인덱스 번호 뽑아내기. k-1은 index가 0부터 시작하기에
        idx = (k-1)//math.factorial(n-1)
        # 숫자를 뽑아서 answer에 쌓기
        answer.append(num_lst.pop(idx))
        # 그 뒤부터 다시 세기 위해 전처리
        k = k % math.factorial(n-1)
        n -= 1

    return answer