[python] 프로그래머스 Lv2. - 줄 서는 방법

코딩테스트 연습 - 줄 서는 방법 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

문제를 이해하는 것이 꽤나 어려웠다.

팩토리얼까지는 접근을 했는데 그 다음 식으로 구현하는 것에 애를 먹었다.

 

문제와 같이 n=3, k=5일 경우 모든 경우의 수를 나열해보면 다음과 같다.

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

따라서 결과는 5번째 방법인 [3,1,2]가 리턴되어야 한다. 

 

줄을 서는 모든 경우의 수는 n을 일렬로 나열하는 경우의 수 n!가지이다.

예를 들어 n=3이고 [1,2,3]을 나열하는 경우의 수는 위와 같이 3! = 3*2*1 = 6가지이다.

이 때, 각 자릿수에서 만들 수 있는 경우의 수를 고려해본다면 각각 2!씩임을 알 수 있다.

즉 모든 경우의 수를 정리한다면 3 * 2!이며 이를 식으로 나타낸다면 n* (n-1)!이다.

결과적으로 모든 경우의 수를 n의 값으로 나눈 (n-1)!은 각 자릿수에서 만들 수 있는 경우의 수에 해당한다.

 

이제 위의 공식을 이용하면 된다. n=3, k=5일 때

1. 각 자릿수에서 가능한 경우의 수 tmp = (n! // n) = (n-1)! = 2!     =>  2가지

2. idx = k//tmp, k = k%tmp  => idx = 2, k = 1   => 즉 각각 1과 2일 때의 경우의 수 2가지씩을 거쳐 3일 때의 경우의 수를 고려하면 되기 때문에 [1,2,3]에서의 idx=2에 해당하는 3이 k=5일때 처음 올 수 있는 수가 된다. 

 

이제 2번을 나머지가 0이 될 때까지 반복하면 된다.

 

import math

def solution(n, k):
    answer = []
    numb = [i for i in range(1, n+1)]
    while (n != 0):
        temp = math.factorial(n) // n
        index = k // temp
        k = k % temp
        if k == 0:
            answer.append(numb.pop(index-1))
        else :
             answer.append(numb.pop(index))

        n -= 1
    
    return answer