[프로그래머스] 줄 서는 방법 _ 문제 풀이



1. 문제

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

2. 풀이

2.1. 시간 초과 풀이

20 이하의 자연수가 문제의 조건입니다. $ 20! $ 의 경우 $ {2.432902008}^{18} $ 입니다. 아래와 같은 풀이 방식으로 접근하면 경우의 수가 너무 커서 시간 초과가 발생합니다.

from itertools import permutations
def solution(n, k):
    a = [x for x in range(1, n+1)]
    return list(permutations(a, n))[k-1]

2.2. 정답 풀이

각 라운드에 맞춰서 해당 라운드에 속하는 숫자를 하나씩 뽑아주고, k 값을 줄여가면서 진행하면 원하는 값을 얻을 수 있습니다.

from math import factorial
def solution(n, k):
    nums = list(range(1, n+1))
    ans = []
    while n != 0:
        temp = factorial(n-1)
        idx, k = (k-1)//temp, k%temp
        ans.append(nums.pop(idx))
        n -= 1
    return ans