Programmers - 줄 서는 방법

문제 링크

처음에 모든 순열 다 만들었다가 시간초과가 발생해서 손으로 써보면서 규칙성을 찾았다.

오름차순으로 정렬된 list A로 만들 수 있는 순열 중 k번째 순열의 첫 번째 값은
A[k/(n-1)!] 이다

ex) [1,2,3,4] 를 모두 선택해서 만들 수 있는 순열을 모두 써보면 첫번째 값이 1인 순열이 6개(3!), 2인 순열이 6개 ... 4인 순열이 6개 임을 알 수 있다.

factorials = [-1 for i in range(21)]
factorials[0] = factorials[1] = 1


def factorial(i):
    if factorials[i] != -1:
        return factorials[i]
    factorials[i] = i * factorial(i-1)
    return factorials[i]


def solution(n, k):

    # li부터 시작해서 만들 수 있는 k번째 순열의 첫번째 값
    def get_first(li, count):
        return li[count//factorial(len(li)-1)]

    perm = [i for i in range(1, n+1)]
    answer = []
    k -= 1  # 0번부터 시작하도록 로직을 구현했음
    while len(perm) > 0:
        first = get_first(perm, k)
        answer.append(first)
        k %= factorial(len(perm)-1)
        perm.remove(first)

    return answer