[LeetCode, 리트코드] Next Permutation

1. Problem

 

정수의 배열이 주어질 때, 이것의 다음 순열을 구하라. 예를 들면

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

2. Solution

 

순열의 성질을 잘 알아야한다. 완전히 역배열된 5,4,3,2,1 과 같은 순열이 있다. 이 다음 순열은? 바로 1,2,3,4,5 다. 이 성질을 이용해서 문제를 풀면 어렵지 않게 풀 수 있다.

더 예를 들어보면 1,6,9,5,4,2,1 이라는 순열이 있다. 그 다음 순열은 어떻게 되겠는가? 9,5,4,2,1은 역배열이다. 그렇다면 6,9,5,4,2,1 에서 6을 대체할 다음 수는 바로 9이다. 왜냐하면 그래야지 나머지 새로운 정배열된 순열을 생성할 수 있기 때문이다. 즉 9,1,2,4,5,6 이 된다.

여기서 규칙을 발견할 수 있다. 먼저 역배열된 순열에서 이 역배열을 깨는 최초의 수를 찾는다. 이 수의 인덱스를 i라 하자. 그리고 이 i보다 큰 인덱스 중에서 이 최초의 수 바로 다음으로 큰 수를 찾는다. 그리고 그것들을 스왑한다.

스왑을 하고 난 후 이 i 인덱스 이후의 순열들을 뒤집는다. 이 규칙을 잘 적용하면 풀 수 있는 문제다.

3. Code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        int j;
        while(i >=0 && nums[i] >= nums[i+1]){
            --i;
        }
        
        if(i == -1){
            reverse(nums.begin(), nums.end());
        }
        else{
            j = i+1;
            while(j < nums.size() && (nums[j] - nums[i]) > 0){
                j++;
            }
            swap(nums[i], nums[j-1]);
            reverse(nums.begin()+i+1, nums.end());
        }
        
        return;
    }
};