문제 설명
📃 문제 링크
n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.
- [1, 2, 3]
- [1, 3, 2]
- [2, 1, 3]
- [2, 3, 1]
- [3, 1, 2]
- [3, 2, 1]
사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.
제한사항
- n은 20이하의 자연수 입니다.
- k는 n! 이하의 자연수 입니다.
입출력 예
| n | k | result |
|---|---|---|
| 3 | 5 | [3,1,2] |
문제 풀이
맨 처음에는 level3의 문제인 줄 모르고, 간단하게 permutations를 이용해서 풀었다. 아래 코드는 모든 경우를 다 구한 다음 정렬해서 k번째 경우를 구하는 코드이다.
from itertools import permutations
def solution(n, k):
people = []
people = [i+1 for i in range(n)]
permute = list(permutations(people, n))
permute.sort()
return list(permute[k-1])시간 초과가 우루루 나왔당!
그래서 모든 경우를 구하지 않고 정답인 한 가지 경우만 구하는 방법을 다시 생각해보았다.
먼저 people 리스트에 1부터 순차적으로 값을 넣어준다.
줄을 설 수 있는 모든 경우의 수는 n!이다. 이 팩토리얼을 이용해서 앞에서부터 한 자리씩 어떤 숫자가 들어가는지 구해준다.
count는 현재 구할 가장 앞자리 수에 따라 각각 몇 가지의 경우가 있는지 구해주는 변수이다. 처음에는 count = 6 // 3 = 2가 된다. 맨 앞자리가 될 수 있는 1,2,3 세 가지 수마다 줄을 설 수 있는 방법은 각각 두 가지가 있다. 즉, 맨 앞자리 수가 1일 때는 [1,2,3], [1,3,2], 맨 앞자리 수가 2일 때는 [2,1,3], [2,3,1], 맨 앞자리 수가 3일 때는 [3,1,2], [3,2,1]이 있다.
여기서 맨 앞자리 숫자 1,2,3을 각각 첫 번째, 두 번째, 세 번째 묶음이라고 한다면 a는 몇 번째 묶음까지 갔는지 알 수 있는 변수이고, 리스트에서 몇 번째 인덱스를 선택해야 하는지 알려주는 변수이다.
그리고 k는 그 묶음에서 몇 개를 더 갔는지 알 수 있는 변수이다. 그래서 k가 0이라면 나누어 떨어진 것이기 때문에 a번째 묶음의 가장 마지막 수일 것이므로 인덱스로 따지면 people[a-1]을 선택해야 한다. k가 0이 아니라면 a번째 묶음까지 모두 채우고, 그 다음으로 k번째 수이기 때문에 people[a]를 선택해준다.
즉, count=2, a=2, k=1일 경우 두 번째 묶음까지 모두 채우고 그 다음 첫 번째 수이기 때문에, 맨 앞자리가 2로 시작하는 묶음까지 모두 채우고 그 다음 맨 앞자리가 3인 묶음의 첫 번째 수이다. 그래서 3을 선택할 수 있도록 people[a]를 선택한다.
선택할 때 pop을 해주어 people 리스트에서 제거해주고, n을 1씩 감소시켜 위의 로직을 3자리수, 2자리수, 1자리수.... 로 반복해준다.
재귀로도 풀 수 있을 것 같지만 재귀는 아직 너무 어렵다. ㅠ.ㅠ
소스 코드
.png)
