LeetCode: 60(순열 시퀀스)(JAVA)

문제 연결

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

설명

전체 솔루션 프로세스는 다음과 같습니다.

1. 주어진 n개의 숫자를 순서대로 나열하고 n을 계산하세요!
   (계승)
2. n이 0이 될 때까지 반복
   1) 현재 n을 n으로 나눕니다!
   
   2) 현재 k가 계승값보다 작아질 때까지 뺄셈과 뺄셈을 몇 번이나 하는지 계산
   3) 현재 숫자 목록에서 뺀 숫자만큼 인덱스의 숫자를 가져와 응답 문자열에 추가한 다음 제거합니다.
   
   4) n-1로 계속
   
3. 반환 결과 문자열

문제의 내용은 전체 길이 n으로 만들 수 있는 순열 중에서 오름차순으로 정렬할 때 k번째 순서에 해당하는 순열을 구하는 문제이다.
문제를 해결하기 위해 k번째 순열을 즉시 계산하는 대신 k를 나누어 순차적 접근 방식을 사용했습니다.

길이 n의 순열이 주어졌을 때, 첫 번째 숫자 이후에 가능한 순열의 수가 특정 숫자(n-1)로 고정된다면!
즉, n이 6이고 첫 번째가 1이면 뒤따르는 순열의 수는 120이고, 다음 첫 번째가 2이면 뒤의 순열의 수는 120입니다.
이것은 모든 숫자에 적용되므로 n이 6일 때 , 이후에 연속적으로 생성되는 순열의 수는 120, 24, 6, 2, 1이 됩니다.
절차.
예를 들어 n이 6이고 k가 150이면 먼저 150이 120보다 크기 때문에 모든 순열을 건너뛰고 첫 번째 순열이 1일 때 시작합니다.
결국 앞자리 숫자 2가 있는 순열 중 하나가 답입니다.
다음 나머지 숫자인 30의 경우 24보다 크기 때문에 해당 숫자를 적용하면 순열에서 두 번째로 오는 숫자를 찾을 수 있습니다.
오름차순이라면 기본적으로 2에 1이 오는 순열인데, 이 경우는 총 24개인데 나머지 숫자가 30이기 때문에 생략하고 2 -> 3 -> .. .. 다음 숫자로 6이 남으므로 1부터 시작하여 남은 수열의 마지막 수열이기도 하다.
얻은.
이를 문제 풀이에 적용하면 주어진 n개까지 사용할 수 있는 숫자를 먼저 목록에 하나씩 입력하고 동시에 n에 대한 계승값을 계산한다.
그런 다음 처음부터 수를 결정하는 while 문을 기반으로 현재 순열 위치 이후에 올 순열의 수인 계승 값을 계산합니다.
다음으로 k의 현재 값에서 현재 팩토리얼 값보다 작아질 때까지 뺄셈 횟수를 세면서 값을 뺍니다.
이때 받은 번호는 이전에 생성한 번호 목록에서 조회할 번호의 순서이므로 목록에서 조회하여 목록에서 제거한다.
이 반복을 통해 순열 전에 숫자를 결정하고 답을 완성할 수 있습니다.

class Solution {
    public String getPermutation(int n, int k) {
        LinkedList<Integer> numbers = new LinkedList<>();
        StringBuilder res = new StringBuilder();
        int factorial = 1, order;

        for (int i = 1; i <= n; i++) {
            numbers.add(i);//사용할 숫자들을 순서대로 list에 추가
            factorial *= i;//n에 대한 factorial 계산
        }

        while (n > 0) {//가장 앞의 숫자부터 순서대로
            factorial /= n;//현재 위치를 제외한 뒷 부분의 순열 길이 
            order = 0;

            while (k > factorial) {//순서 계산
                k -= factorial;
                ++order;
            }

            res.append(numbers.remove(order));//남은 숫자들 중 해당 순서에 해당하는 숫자를 가져와 추가
            --n;
        }

        return res.toString();
    }
}

결과