[LeetCode] 60. Permutation Sequence (Java) - 팩토리얼을 이용한 K번째 순열 구하기

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:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.


자연수 n과 k를 매개변수로 받아 n자리 숫자를 사전식으로 나열했을 경우 k번째 숫자는 무엇인지 구하는 문제이다.
모든 순열을 직접 구하지 않고 첫 번째 자리부터 차례대로 어떤 숫자가 들어갈지 수학적으로 계산하는 방식을 사용하였다.
첫 번째 자리에 특정 숫자가 나올 경우 남은 자리의 올 수 있는 순열은 (n-1)!개이다.
예를 들어 n이 4일 경우 가장 앞에 자리 숫자는 1~6이면 1 7~12는 2 13~18는 3 19~24는 4 (n-1)!의 개수에 따라 자리 숫자가 달라지는 것을 알 수 있다.
따라서 List를 통해 사용한 숫자를 빼가면서 마지막 자리까지 반복하여 숫자를 구해주면 난이도 치고는 상당히 쉽게 풀리는 문제였다.

class Solution {
    public String getPermutation(int n, int k) {
        if(n==1) return "1";
        int[] arr = {1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
        List<Integer> lst = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=n; i++) lst.add(i);
        k--;
        for(int i=n-2; i>=0; i--){
            int q = k/arr[i];
            sb.append(lst.get(q));
            lst.remove(q);
            k = k%arr[i];
        }
        sb.append(lst.get(k));
        return sb.toString();
    }
}