프로그래머스 LV2 - 줄 서는 방법

문제 링크

내 풀이

from itertools import permutations

def solution(n, k):
    person = [i for i in range(1, n + 1)]
    for i, permutation in enumerate(permutations(person, n)):
        if i == k - 1:
            return list(permutation)

정답 풀이

import math

def solution(n, k):
    # 1부터 n까지의 숫자 리스트 생성
    person = [i for i in range(1, n + 1)]
    # 결과를 저장할 리스트
    result = []
    # k를 0-based index로 변환
    k -= 1
    
    while n > 0:
        # n-1개의 순열 수
        fact = math.factorial(n - 1)
        # 현재 자릿수의 인덱스 결정
        index = k // fact
        # 결정된 인덱스의 숫자 추가
        result.append(person.pop(index))
        # 다음 k 값 갱신
        k %= fact
        # n 감소
        n -= 1
    
    return result

풀이 해석

• n-1개의 순열 수를 k에 나누며 fact와 k 최신화
• 각 자리수를 결정할 때마다 가능한 순열의 수를 이용해
• k번째 순열을 직접찾아내는 방법을 사용함

배울점

• k번째 수열을 직접 찾아내는 알고리즘
• permutations의 시간복잡도 보다 효율적인 코드 설계