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