LeetCode 60번 Permutation Sequence

https://leetcode.com/problems/permutation-sequence/

---

문제 파악

이 문제는 주어진 숫자 n에 대해 [1, 2, 3, ..., n]의 모든 순열을 생성하고, 그 중에서 k번째 순열을 반환하는 문제이다.

모든 순열은 사전순으로 정렬되어 있다. 이를 해결하기 위해 직접적으로 모든 순열을 생성하는 것보다 더 효율적인 방법을 사용할 수 있다.

순열의 정의 → n개의 원소로 구성된 순열은 총 n!개의 고유한 순열을 가진다.

접근 방법

가장 간단한 방법은 1 ~ n의 숫자로 만들 수 있는 모든 순열을 오름차순으로 정렬한 다음에 k번째 순열을 찾아서 반환하면 된다. 물론 최대 범위가 $9! = 362880$이다. $10^8$보다는 작아서 가능하지만, 시간 소모가 매우 크다.

팩토리얼을 이용해서 각 숫자가 어떤 위치에 올 수 있는지를 계산해서 k번째 순열을 직접적으로 생성한다. 사전 순으로 계산하여 해당 위치의 숫자를 결정하여 푼다!

코드 구현

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        ans = []
        nums_list = []
        for i in range(1, n+1):
            nums_list.append(i)
            
        def backtracking(curr):
            if len(curr) == n:
                ans.append(''.join(map(str,curr)))
                return
            
            for num in nums_list:
                if num not in curr:
                    curr.append(num)
                    backtracking(curr)
                    curr.pop()
                
        backtracking([])
        return ans[k - 1]

처음에는 이렇게 코드를 짜서 시간 초과가 떴다.

from typing import List
from math import factorial

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        # 초기화: 숫자 리스트와 k를 0 인덱스 기반으로 변환
        nums = list(range(1, n + 1))
        k = k - 1  # 1,2,3...에서 0,1,2,3... 로 변환

        # 결과 문자열 초기화
        result = []

        # 모든 자리수에 대해 계산
        for i in range(n):

            # 현재 자리에서 올 숫자의 인덱스 계산

            # 현재 자리에서 남은 숫자들의 순열 개수 계산
            fact = factorial(n - 1 - i)

            # 인덱스 계산
            index = k // fact
            k %= fact

            # 결과에 숫자를 추가하고 리스트에서 제거
            result.append(str(nums[index]))
            nums.pop(index)

        return ''.join(result)

수학적 계산을 통해 "순열의 k번째 수열"을 찾는 방법은, 주어진 숫자의 팩토리얼 값을 사용하여 각 자릿수의 값을 결정하는 것이다. 이 방법은 모든 순열을 생성하지 않고도 원하는 순열을 직접 계산할 수 있기 때문에 시간 복잡도를 크게 줄일 수 있다.

여기서 문제의 핵심은 팩토리얼(factorial) 값을 활용하여 주어진 위치 k에 해당하는 순열을 직접 계산하는 것이다.