1. 문제 설명

줄 서는 방법

2. 문제 분석

n명을 줄 세우는 경우의 수 중 k번째에 해당하는 경우의 수를 구한다.

• 파이썬의 permutation 모듈은 시간 효율성이 떨어지기 때문에 직접 factorial 값을 통해 하나씩 구한다.

1. 매 차례마다 line 안에 남아 있는 n 명 중 앞 자리에 설 사람이 누구인지 찾는다. n명이 남아 있기 때문에 각 사람마다 앞에 올 수 있는 경우의 수는 (n-1)!이다. k번째에 해당하는 앞 자리 사람은 k // (n-1)!에 해당하는 사람이다.

2. 나머지가 0이라면 다음 칸으로 넘어가지 않기 때문에 1을 빼줘야 한다.

3. 맨 앞 자리 사람을 line에서 빼고 result에 차례대로 넣어준다.

4. n-1 명이 남았다. k는 앞의 앞 자리 사람을 구하고 남은 나머지 안에서 새롭게 구해야 하기 때문에 k%n이 된다.

n=3, k =5를 통해 위 알고리즘을 확인해보자. 세 명은 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 순서대로 줄을 설 수 있다.

1. 맨 앞 자리 사람을 구한다. 5번째 중 맨 앞 자리에 누군가가 할당되는 경우는 (n-1)!=2!를 나눠준다. (2, 2, 1)이므로 3이 온다는 사실을 알 수 있다.

2. line 리스트의 인덱스가 0부터 시작하기 때문에 몫인 2를 그대로 사용할 때 마침 3번째로 서 있던 숫자 3번이 빠져 나오게 된다.

3. 3이 빠진 뒤 line에는 [1, 2] 두 명이 남아 있다. 처음 k=5에서 2!을 나눈 나머지인 1을 통해 다시 다음 차례 맨 앞에 올 사람을 구하자.

4. 2를 1!로 나눈다는 건 (1==[1,2], 1==[2,1])에서 첫 번째 케이스의 1을 골라야 한다. 하지만 이때 몫인 1을 그대로 사용한다는 건 1이 아니라 2를 뽑는 게 된다. 따라서 인덱스에 1을 빼준 0을 쓴다.

5. 이와 같은 방법으로 마지막 0!을 통해 (1==[2])의 첫 번째 케이스 2를 골라야 한다. 그런데 이 역시 마찬가지로 몫인 1로 접근하려면 인덱스에 1을 빼줘야 한다.

• k의 나머지에 따라 인덱스 값을 조절하는 게 이 문제를 푸는 데 있어서 가장 힘든 부분이었다.

3. 나의 풀이

import math
def solution(n, k):
    line = [i for i in range(1, n+1)]
    result = []
    while line:
        fac = math.factorial(n-1)
        # 맨 앞의 자리수를 정하기 위해 건너뛸 크기: factorial n-1
        idx = int(k//fac)
        if k%fac == 0: idx -= 1
        # 나머지가 0일 때에는 다음 칸으로 넘어가지 않는다. 이때 리스트 line의 인덱스 -= 1을 해야 접근 가능
        k = k%fac
        # 지금 맨 앞에 설 사람이 빠진 뒤에 반복하기 위함
        result.append(line.pop(idx))
        n -= 1
    return result