[프로그래머스] 줄 서는 방법 #파이썬 #수학 #level3 [연습문제]

https://programmers.co.kr/learn/courses/30/lessons/12936#

코딩테스트 연습 - 줄 서는 방법

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]

입출력 예시 설명

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

풀이

가장 간단한 방법은 정말 다 만들어서 정렬 후 순열[k-1]를 반환하는 것입니다. 물론 그렇다면 3단계 문제가 아니겠죠. 이 경우 시간 초과가 발생합니다.

 

시간 초과를 피하는 방법 또한 간단합니다. 현재 병목이 발생하는 부분은 순열을 계산하는 부분, 사실 k-1번째가 아닌 나머지 순열의 요소는 계산될 필요가 없습니다. 이 경우 답을 구하는 수학적인 방법이 있을 터입니다. 문제에서 주어진 상황을 다시 봅시다. 3명의 사람을 세우는 방법의 수는 3! = 6가지입니다.

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

4명의 사람을 세우는 방법의 수는 4! = 24가지이며, 4 x 3!입니다. 즉, 0번째 자리가 달라지기 위해서는 (n-1)! 번의 가짓수가 필요하다는 말이 되겠네요. 1번째 자리는 (n-2)!, n-1번째 자리는 (n-n)!마다 변경됩니다.

문제를 반대로 생각해봅시다. n = 4, answer = [1, 4, 2, 3]이면 k는 몇일까요?

• [1, 2, 3, 4]
• [1, 2, 4, 3]
• [1, 3, 2, 4]
• [1, 3, 4, 2]
• [1, 4, 2, 3], k = 5

n = 4, k	자릿수	자릿수를 바꾸기 위해 필요한 경우의 수	몫	나머지	number pool	answer
4	1	3! = 6	0	4	[1, 2, 3, 4]	[1]
4	2	2! = 2	2	0	[2, 3, 4]	[1, 4]
0	3	1! = 1	0	0	[2, 3]	[1, 4, 2]
0	4	0! = 1	0	0	[3]	[1, 4, 2, 3]

k가 1을 기준으로 시작하기 때문에... 1 줄여준 상태에서 시작합니다. k를 자릿수를 바꾸기 위해 필요한 경우의 수로 나누고, number pool[몫]을 answer에 추가한 뒤 number pool에서 제거해줍니다. 나머지는 k로 취합니다. 말이 너무 복잡한가요? 개발자는 코드로 말하는 법! 코드를 살펴봅시다.

import math

def solution(n, k):
    k -= 1
    answer = []
    numbers = list(range(1, n+1))
    
    for i in range(n, 0, -1):
        div, k = divmod(k, math.factorial(i-1))
        answer.append(numbers.pop(div))
        
    return answer