[ Lv 3 ] 줄 서는 방법

풀이 과정

1. 현재 자리수가 맨 앞자리라고 할때, 뒷자리 가능한 경우의 수는 (n-1)!이다.
   • 따라서, 맨 앞자리가 1일때는 0(n-1)!, 맨 앞자리가 2일때는 (n-1)!(n-2)!, ... 의 범위를 갖게 된다.
2. 따라서, 맨 앞자리부터 범위를 구한다.
   • 해당 범위라면, 현재 남아있는 경우의 수에서
     1. 범위의 최솟값을 빼주고
     2. 사용 가능한 숫자 리스트에서 제거
     3. 범위 조정
   • 범위를 조정하는 방식은 (n-1)!에서 (n-1)을 나누어주어 (n-2)!로 만들어 준다.
   • 해당 범위가 아니라면, 범위를 조정해가면서 검사한다.
3. 매 순간 범위에 해당하는 경우를 answer에 넣어주면 된다.

---

소스 코드

---

def solution(n, k):
    answer = []
    candidate = list(i+1 for i in range(n))
    # 맨 앞자리가 고정되었을때 뒷자리 가능한 경우의 수
    p = factorial(n-1) 
    div = n-1

    while div >= 0:
        fr = 0
        to = p
        for idx in range(len(candidate)):
            if fr <= k and k <= to: 
                # 현재 범위 내에 들어가는 경우
                answer.append(candidate[idx])
                # 현재 범위의 최솟값을 빼줌
                k = k - fr
                if div != 0:
                    # 맨 앞자리가 무엇이 나오는지 알음. 
                    # 따라서 다음 자리를 구해야 하므로 n-1자리를 검사했다면
                    # factorial의 결괏값에 n-1을 나누어주면 n-2!이 나옴.
                    p = p // div 
                # 자리수 조정
                div -= 1 
                del candidate[idx] # 현재 사용된 숫자는 지워줌.
                break
            else: 
                # 현재 범위 내에 들어가지 않으면 다음 범위
                fr = fr + p
                to = to + p

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges