[프로그래머스/Python] 줄 서는 방법

📌 문제

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

📌 풀이

풀이 1 - (성공)

1. 1부터 n까지의 수로 리스트("_list")를 생성한다.
2. 리스트의 원소로 만들수있는 모든 순열 조합을 리스트("list")로 생성한다. (순열 조합으로 만들었을 때 이미 사전순으로 정렬되어 나옴)
3. 순열 조합에서 k-1번째 값을 반환한다. (k-1을 사용하는 이유는 파이썬의 리스트 인덱스가 0부터 시작하기 때문이다)

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

풀이 2 - (12,13번 테스트케이스 시간 초과)

주어진 코드는 itertools의 permutations 함수를 사용하여 n개의 숫자로 이루어진 순열을 모두 생성한 다음, 그 중에서 k번째 순열을 반환하려고 한다. 그러나 이 코드는 순열의 개수가 매우 커질 때(특히 n이 큰 경우) 성능 문제가 발생할 수 있다.

이러한 성능 문제를 해결하려면 다른 방식으로 접근해야 한다. 순열을 구하는 대신, 팩토리얼 개념을 통해 k번째 순열을 직접 계산하는 방법을 사용할 수 있다.

def solution(n, k):
    answer = []
    _list = [i for i in range(1, n + 1)]
    
    k -= 1  # k를 0-based 인덱스로 변환
    
    factorial = 1
    for i in range(1, n):
        factorial *= i
    
    for i in range(n - 1, -1, -1):
        index = k // factorial
        answer.append(_list.pop(index))
        k %= factorial
        if i > 0:
            factorial //= i
    
    return answer