---
description: '210720'
---

# 줄 서는 방법

```python
from itertools import product
def solution(n, k):
    lst = list(map(str, list(range(1, n+1))))
    pdt = list(product(*([lst] * n)))
    idx = 0
    for p in pdt:
        if len(set(p)) == n:
            if idx == k-1:
                return list(map(int, p))
            else:
                idx += 1
```

![](https://2275555537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MNN4u9o9noCQwX8pO35%2F-MezFlcZ_vC0yrAR3hrr%2F-MezJ8DKfw6Fa7s6yLvY%2Fimage.png?alt=media\&token=68506081-5c5e-4592-b29e-f5101834b3f8)

시간초과가 나는 이유는 시간복잡도가 $$O(N^2)$$ 이기 때문이다. 적어도, $$O(N logN)$$ 아니면 $$O(N)$$을 바라는 듯 하다.

```python
'''
https://programmers.co.kr/learn/courses/30/lessons/12936
줄 서는 방법
[풀이]
1. 각 경우의 수는 FACTORIAL 만큼 존재
=> 미리 factorial을 구해놓는다
=> math.factorial을 써도 가능하다
2. 사전 순으로 나열할 때 가장 처음 등장하는 수는
range(1, n+1)에서 (k-1) // (n-1)! 에 해당하는 순서의 수이다.
=> 반복문으로 이를 구한다
=> 매번 구해지는 순서는 결과 리스트에 추가
'''
def solution(n, k):
    dp = [1] + [0] * n
    for i in range(1, n + 1):
        dp[i] = i * dp[i - 1]

    lst = list(range(1, n + 1))
    ret = []
    for i in range(n - 1, -1, -1):
        idx = (k - 1) // dp[i]
        ret.append(lst.pop(idx))
        k = k % dp[i]
    return ret
```

![](https://2275555537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MNN4u9o9noCQwX8pO35%2F-MezFlcZ_vC0yrAR3hrr%2F-Mf3M3AOtfJOm4lf5VMM%2Fimage.png?alt=media\&token=fc4ed368-7090-430a-911b-e342c0315476)
