[LeetCode] 60. Permutation Sequence

숫자를 생성하고 팩토리얼을 미리 계산한 후 k번째 순열이 어떤 수로 구성되어있는지 확인하는 문제이다.

아마 많은 의심이 들 부분은 마지막 결괏값을 구하는 부분일텐데 간략히 설명하자면 다음과 같다.

1. n개의 숫자로 만들 수 잇는 순열 수는 n! ex) n이 4라면, 순열은 24가지이며 각 요소가 가지는 그룹의 크기는 3! = 12가지 이다. ex) 1로 시작하는 순열 6개, 2로 시작하는 ...
2. k를 그룹의 크기(3!)로 나누어 몫을 구하면, 어떤 그룹에 속하는지 알 수 있음
   ex) k=9일 때, 9 / 6 = 1이므로 두 번째 그룹(2로 시작)에 속함.
3. 첫 번째 숫자를 결정한 후, k를 갱신하고(k = k % 3!) 과정을 반복하며 각 자리의 숫자를 결정

😎풀이

function getPermutation(n: number, k: number): string {
    let result = ""
    const numbers = Array.from({length: n}, (_, i) => i + 1)
    
    const factorial = [1]
    for (let i = 1; i <= n; i++) {
        factorial[i] = factorial[i-1] * i
    }
    
    
    // n번째를 지목하는 k를 인덱스 기준 숫자로 변환
    k--
    
    // n-1부터 0까지 반복
    for (let i = n - 1; i >= 0; i--) {
        // 현재 자리수에 올 숫자의 인덱스 계산
        const index = Math.floor(k / factorial[i]);
        
        // 계산된 인덱스의 숫자를 결과에 추가
        result += numbers[index];
        
        // 사용된 숫자 제거
        numbers.splice(index, 1);
        
        // k 갱신
        k %= factorial[i];
    }
    
    return result;
}