프로그래머스 줄 서는 방법

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

조합에서의 순서를 찾는 문제였다.
문제를 구조화시켜보면 마치 캐시메모리에서 직접사상을 연결하는 방식과 매우 유사해 보였다.

시간 초과가 난 코드

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

당연히 시간초과가 나겠지하고 돌려봤던 코드이다. 역시나 시간초과

캐시메모리에서 직접사상에 연관시키는 방식을 생각하고 구현하였다.

숫자 배열에서 n값을 줄여나가며 어떤 위치에 어떤 값이 와야하는지를 구하였다.

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