LeetCode: 60번 (Permutation Sequence) [JAVA]

문제 링크

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

Permutation Sequence - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 n만큼 숫자들을 순서대로 담은 List 생성, n!을 계산(factorial)
2. n이 0이 될때까지 반복
   1) 현재 앞서 계산한 n!에서 현재 n만큼을 나눗셈
   2) 현재 k가 factorial보다 작아질 때까지 해당 값을 빼기, 뺀 횟수를 계산
   3) 현재 숫자들을 넣어놓은 List에서 뺀 횟수만큼의 index의 숫자를 가져와 답 string에 추가 후 제거
   4) n-1 진행
   
3. 결과 답 string 반환

 문제의 내용은 전체 길이 n만큼을 가지고 만들 수 있는 순열에서, 오름차순 정렬을 했을 때 k번째 순서에 해당하는 순열을 가져오는 문제이다. 해당 문제를 풀기 위해 한 번에 k 번째 순열을 계산하기 보다는, k를 나누어 순차적으로 접근하는 방법을 사용했다.
 만약 길이가 n인 순열에서, 가장 맨 앞자리가 특정 숫자로 고정이 된 상태에서 그 뒤로 올 수 있는 순열의 가짓수는, (n-1)!이 된다. 즉, n이 6일 때 맨 앞이 1이라면 그 뒤에 올 수 있는 순열의 개수가 120개가 올 수 있고, 그 다음으로 맨 앞이 2라면 그 뒤에 올 수 있는 순열의 개수가 120개 된다. 이는 각 자릿수에 모두 적용이 되어, n이 6일 때 순차적으로 뒤에 만들어지는 순열의 개수들이 120, 24, 6, 2, 1이 되는 것이다. 이를 문제 해결에 적용할 수 있는데, 주어진 k번째 순서에 대한 순열을 해당 방식을 바탕으로 앞의 숫자부터 정해나가는 방식이다.
 예를 들어 n이 6이고 k가 150이라면, 우선 150이 120보다 크기 때문에 우선 순열의 맨 앞이 1일 때의 순열들은 모두 건너뛰고 시작하게 된다. 결국 맨 앞자리가 2인 순열들 중의 하나가 답이 된다. 그 다음 남은 수인 30에 대해서, 이 또한 24보다 크기 때문에 이를 적용하면 순열의 두 번째 자리에 올 수를 구할 수 있다. 기본적으로 오름차순이라면 2 다음에 1이 오는 순열이지만, 이 경우도 총 24가지가 있지만 남은 수가 30이기 때문에 이를 건너뛴 다음 숫자인 2 -> 3 -> ... 형태의 순열 중 하나가 된다. 또 그 다음 순서의 숫자에 대해서도 6이 남기 때문에 1로 시작하는 남은 수열의 마지막 순서가 된다. 결국 2 -> 3 -> 1 -> 6 -> 5 -> 4라는 형태를 얻을 수 있다.
 이를 문제 해결에 적용하면, 우선 주어진 n만큼 사용할 숫자들을 순서대로 list에 추가하고, 동시에 n에 대해 팩토리얼 값을 계산한다. 그 다음 가장 앞부터 숫자를 결정하기 위해 while문을 바탕으로, 현재 순열 위치 뒤에 올 순열들의 개수인 팩토리얼 값을 계산한다. 그 다음 현재 k값에 대해 현재 팩토리얼 값보다 작을 때까지 값을 빼고, 동시에 몇 번 뺐는 지 횟수를 count한다. 이 때 얻은 횟수가 앞서 만든 숫자 list에서 가져올 숫자의 순서기 때문에, 이를 해당 list에서 가져오고 list에서 제거해준다. 이렇게 반복을 통해 순열의 앞에서 숫자를 결정해주며 답을 완성할 수 있다,

 

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();
    }
}

결과