[Python/파이썬] 프로그래머스 Lv2 - 줄 서는 방법

 

---

Solution.py

처음에는 permutations로 순열을 이용해 문제를 풀었는데

Lv2 답게 간단하게 문제가 풀릴일이 없이 효율성, 시간 초과로 실패했습니다.

 

이 문제를 풀기 위해서는 수학적으로 접근해야하는데,

먼저 맨 앞의 숫자가 1일 때, 1을 맨 앞의 원소로 갖는 순열은 [1, 2, 3] , [1, 3, 2] 로 총 두 가지 입니다.

이 경우의 수는 (n - 1)!을 계산했을 시 나올 수 있는 경우의 수가 됩니다.

파이썬의 math 모듈에서 factorial() 팩토리얼 메서드를 제공 해줍니다,

 

그 다음으로는 이 문제에서 k 번째 방법을 반환하라고 했는데, k의 수를 인덱스 값으로 변환하여 k - 1 을 해줘야합니다.

k 번째에 있는 수를 구하기 위해서

(k - 1) // math.factorial(n - 1) 으로 몫을 구해 k 번째 순열에 첫 번째 있는 값의 인덱스를 찾습니다.

여기서는 k가 5이 므로 위 식에 대입했을 시 index 값은 2가 되며 arr[2]에 있는 값이 k 번째 순열의 첫 번째 값이 됩니다.

그러면 첫 번째 숫자가 결정 되었으므로, 다음에 올 숫자를 구하기 위해

k는 k % math.factorial(n - 1)으로 나머지 값이 되며 n을 1씩 감소 시켜 그 다음에 오는 원소를 구해갑니다.

 

정답 코드

import math

def solution(n, k):
    arr = [i for i in range(1, n + 1)]
    answer = []
    
    while arr:
        a = (k - 1) // math.factorial(n - 1)
        answer.append(arr.pop(a))

        k = k % math.factorial(n - 1)
        n -= 1

    return answer