[Python] 줄 서는 방법 - 프로그래머스

해당 글은 프로그래머스 Level2 '줄 서는 방법'을 다룬다.

문제

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

프로그래머스

 

설명

일반적인 순열문제로 풀면 효율성 테스트케이스에서 실패한다.

그래서 숫자간 규칙을 찾아내서 구해야한다.

팩토리얼을 통해 answer의 맨 앞부터 채워나가면 된다.

arr = [1, 2, 3], fac(2) = 2

k : 5~6 일 때, (k-1)//fac = 2, arr[2] = 3

k : 3~4 일 때, (k-1)//fac = 1, arr[1] = 2

k : 1~2 일 때, (k-1)//fac = 0, arr[0] = 1

 

* arr = [1, 2, 3], fac(2) = 2

k : 5일 때, (k-1)//fac = 2, arr[2] = 3, k = k%fac = 1

* arr = [1, 2], fac(1) = 1

k : 1일 때, (k-1)//fac = 0, arr[0] = 1, k = k%fac = 0

* arr = [1], fac(0) = 1

k : 0일 때, (k-1)//fac = -1, arr[-1] = 1, k = k%fac = 0

 

코드

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