Programmers - 줄 서는 방법[파이썬(python)]

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12936

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

 

문제 설명

명의 사람이 일렬로 줄을 서고 있습니다. 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]

 

---

문제 풀이

해당 문제는 팩토리얼과 관련이 많은 문제이다. 위의 예시와 같이 3명은 다음과 같은 경우로 줄을 설 수 있다.

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

3명이 줄을 서는 경우는 3!으로 총 6가지의 경우가 있다. 줄을 서는 경우가 사전 순으로 나열되어있다고 한다면 가장 앞자리의 숫자가 바뀌는 지점은 줄을 서는 경우 6개를 인원수 3으로 나눈 2번째 다음 지점부터 수가 바뀐다.

여기서 2는 (n-1)! 이 된다. 만약 4명이 줄을 서는 경우라고 한다면 경우의 수는 총 4!으로 24가 되고 (n-1)! 인 6번째마다 그 다음 지점부터 앞자리 숫자가 바뀌게 된다. 

 

위에 예시에서 k=4인 4번째 경우를 구한다고 가정해보자.

4번째 경우의 가장 앞자리 수를 구하기 위해선 4를 (n-1)!인 2로 나누어 주어 4/2 = 2 가된다.

여기서 구한 2는 앞자리의 수가 변환 횟수를 의미하는데 2번 바뀌었다면 3이 되어야 한다.(1 -> 2 -> 3) 하지만 실제로 숫자가 변하는 지점은 (n-1)! 의 다음 지점이므로 k에서 1을 뺀 수에 (n-1)! 을 나누어 주어야 실제 숫자를 알 수 있다.

즉 (k-1)/(n-1)! 을 구해주면 k번째 경우에서 가장 앞자리 수를 알 수 있다. 위의 예시의 경우 (k-1)/(n-1)! = 1.5이고 정수를 취해주면 1이 된다. 다시 말해 3명이 줄을 서는 4번째 경우 가장 앞의 숫자는 처음 1에서 값이 한번 변하여 2가 된다는 것을 알 수 있다.

 

3명 중 가장 앞에 오는 사람을 알았으면 이후는 위와 동일한 방법을 적용한다. 이후엔 2명을 줄 세우는 문제로 변하기 때문이다.

2명을 줄 세울 때 몇 번째가 되는지는 k를 (n-1)!으로 나눈 나머지를 구함으로써 알 수 있다. 위 예시에서 4를 (n-1)!으로 나눈다면 나머지는 0이다 나머지가 0이라것은 2명을 줄 세우는 경우에서 가장 마지막인 2! 번째를 의미한다. k=2가 되는 것이다. (만약 나머지가 0이 아니라면 k는 그대로 나머지를 사용하면 된다.)

따라서 가장 앞에 숫자 2를 제외한 [1, 3]을 줄 세우는 방법 중 n=2, k=2일 때 가장 앞에 오는 수를 구하는 문제를 푸는 것과 동일하다.

 

위와 같은 과정을 n번 반복하며 배열에 수를 추가하면 답을 구할 수 있다.

 

구현 코드

코드 링크 : 줄 서는 방법

import math

def solution(n, k):
    arr = []
    num_person = n
    person = [i+1 for i in range(n)]
    
    for _ in range(n):
        nf = math.factorial(num_person-1)
        arr.append(person[int((k-1)/nf)])
        del person[int((k-1)/nf)]
        temp_k = k%nf
        num_person -= 1
        if temp_k == 0:
            k = math.factorial(num_person)
        else:
            k = temp_k

    return arr