[LeetCode] 60. Permutation Sequence(Java, Hard)

## 접근방법

---

순열 문제는 자주 나온다. 보통은 그 다음 순열을 물어보는데, 이 문제는 전체 순열에서 순서를 물어보고 있다는 차이점이 있다.

 

 

 

순열을 생각해보면, 1234에서 가장 앞자리가 2가 되려면 3!만큼의 순서가 지나야 될 수 있다. 즉, 어떤 순서를 구할 때, 바로 다음을 구하는 것보다 팩토리얼을 이용해서, 순서를 차감해가는 방식을 사용할 것이다.

 

 

 

그림과 함께 이해를 해보도록 하자.

 

 

 

n은 6이고 k는 77이라고 가정해보자, 어떤 수를 넣어도 원리는 동일하다.

 

 

 

 

 

첫번째 그림은 초기 상태인 123456을 의미한다. 

 

 

 

두번째 그림은, 77 - 5! >= 1이다. 따라서, 1에서 가장 가깝게 큰 2로 변경해준다.

 

 

 

세번째 그림은, 17 - 3! >= 1이므로, 3에서 가장 가깝게 큰 4로 변경해준다.

 

 

 

네번째 그림은, 9 - 3! >= 1이므로, 4에서 가장 가깝게 큰 5로 변경해준다.

 

 

 

최종적으로 k가 1이되면 과정을 종료한다.

 

 

 

## 해설코드

---

class Solution {
    public String getPermutation(int n, int k) {
        int[] fact = new int[n + 1];
        int factIdx = n;
 
        char[] str = new char[n];
        for(int i = 1; i <= n; i++)
            str[i - 1] = (char)(i + '0');
        
        fact[1] = 1;
        for(int i = 2; i < fact.length; i++){
            fact[i] = fact[i - 1] * i;
        }
        
        while(k > 1){
            while(factIdx > 0 && k - fact[factIdx] < 1){
                factIdx--;
            } 
            
            if(factIdx > 0){ 
                k -= fact[factIdx];
                int tmp = n - factIdx;
                
                // Swap
                for(int j = n - factIdx; j < str.length; j++){
                    if(str[n - factIdx - 1] < str[j]){
                        char c = str[n - factIdx - 1];
                        str[n - factIdx - 1] = str[j];
                        str[j] = c;
                        break;
                    }
                }
            }
        }
        
        return String.valueOf(str);
    }
}