[프로그래머스] 줄 서는 방법 (level2, python)

🏝 문제 설명

 

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! 이하의 자연수 입니다.

---

입출력 예

3

5

[3,1,2]

---

입출력 예시 설명

 

입출력 예 #1
문제의 예시와 같습니다.

---

 

🏝 풀이 코드

import math

def solution(n, k):
    answer = []
    people = [i for i in range(1, n+1)]
    
    for i in range(1, n+1):
        divider = math.factorial(n-i)
        idx = k // divider
        if k % divider == 0:
            idx -= 1

        answer.append(people[idx])
        people.pop(idx)
        k -= idx * divider

    return answer

 

규칙 찾기 문제다.

 

브루트포스로 구하면 어마어마한 연산 횟수에 의해 시간초과가 난다.

문제에서 나온 케이스를 바탕으로 보자.

 

• [1, 2, 3]
• [1, 3, 2]
• [2, 1, 3]
• [2, 3, 1]
• [3, 1, 2]
• [3, 2, 1]

 

3명을 순서대로 줄을 세우는 방법을 사전순으로 정렬한 결과다.

가장 앞의 사람을 보면, 1번, 2번, 3번 사람이 나오는 구간이 있다.

 

각 구간의 크기는 (n-1)!이다.

따라서 (n-1)!의 구간이 총 n개 있으므로 n!의 줄 세우기 결과가 나오는 것이다.

 

answer 배열에 가장 첫 번째 자리에 올 사람을 구하는 방법은 문제에서 주는 k를 활용하는 것이다.

k번째 사람이 어느 구간에 속하는지를 판단한다. 구간의 크기가 (n-1)!이므로, k // (n-1)!을 해준다. 이것을 뒤에 나오는 people의 index로 쓴다.

people 배열에 1번 사람부터 n번 사람까지 배치시켜놓고, index + 1번째 번호의 사람이 answer에 들어가야 하므로, index로 접근하면 된다.

 

예외의 경우, k가 (n-1)!의 배수라면 index 초과가 나기 때문에 index-1을 해준다.

예를 들어, n=3, k=6인 경우, 6은 (n-1)!인 2의 배수이기 때문에 idx가 3이 나온다. n=3이면 people 배열 속 사람은 3명이므로 index가 0, 1, 2로 3은 존재하지 않는다. 이 경우를 예외처리하기 위해서 index-1을 해준다.

 

answer에 집어놓고, 해당 사람은 줄을 세웠으니 대기열에서 해당 사람을 제거한다. (people pop)

그 다음 반복문에서는 k번째 사람이 아니라 앞의 idx번의 구간을 지난 후의 사람을 찾아야 하므로 idx * divider를 빼준다.