[LeetCode] 60. Permutation Sequence

https://leetcode.com/

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1."123"
2."132"
3."213"
4."231"
5."312"
6."321"

Given n and k, return the k^th permutation sequence.

 

Example 1:

Input: n = 3, k = 3
Output: "213"

 

Example 2:

Input: n = 4, k = 9
Output: "2314"

 

Example 3:

Input: n = 3, k = 1
Output: "123"

 

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

 

Code :

var getPermutation = function(n, k) {
    // 팩토리얼 값을 저장할 배열
    let factorial = [1];
    // 1부터 n까지의 수를 저장할 배열
    let nums = [];
    // 결과를 저장할 변수
    let result = "";

    // 팩토리얼 사전 계산
    for (let i = 1; i <= n; i++) {
        factorial[i] = factorial[i - 1] * i;
        nums.push(i);
    }

    // k를 0부터 시작하도록 1 감소시킴
    k--;

    // k번째 순열 계산
    for (let i = 1; i <= n; i++) {
        // 현재 인덱스 계산
        let index = Math.floor(k / factorial[n - i]);
        // 결과에 해당하는 숫자 추가
        result += nums[index];
        // 사용된 숫자는 배열에서 제거
        nums.splice(index, 1);
        // 다음 순열을 위해 k 갱신
        k -= index * factorial[n - i];
    }

    return result;
};

 

Solutions Code :

var getPermutation = function(n, k) {
    // 팩토리얼을 미리 계산하여 사용하기 위한 배열
    const factorial = [1];
    
    // 1부터 n까지의 팩토리얼 계산하여 배열에 저장
    for (let i = 1; i <= n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }

    // 1부터 n까지의 숫자를 담은 배열 생성
    const numbers = Array.from({ length: n }, (_, i) => i + 1);

    // k번째 순열을 담을 변수
    let result = '';

    // k를 0부터 n-1까지 반복하면서 계산
    for (let i = 0; i < n; i++) {
        // 현재 자릿수의 인덱스를 계산
        const index = Math.floor((k - 1) / factorial[n - 1 - i]);
        
        // 해당 인덱스의 숫자를 결과에 추가
        result += numbers[index];
        
        // 사용한 숫자를 배열에서 제거
        numbers.splice(index, 1);
        
        // k를 갱신
        k = (k - 1) % factorial[n - 1 - i] + 1;
    }

    return result;
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode