[LeetCode] Next Permutation (C++)

문제 링크: https://leetcode.com/problems/next-permutation/description/

Next Permutation - LeetCode

1. 순열의 순서는 어떻게 정해질까?에 대한 의문을 직접 구현 하는 문제다. C++의 경우 next_permutation 함수를 직접 구현한다고 생각하면 된다.

 

2. 접근 방법

위 문제와 같이 아무 배열이 주어지고, 이 다음 순열을 어떻게 구하는 방식은 어떻게 될까?

#1 [2, 4, 3, 1, 3] -> [2, 4, 3, 3, 1]
#2 [4, 3, 2, 1] -> [1, 2, 3, 4]
#3 [5, 1, 4, 3, 2] -> [5, 2, 1, 3, 4]

위 예시를 통해 접근해보자

#1은 3~4번 인덱스의 값들이 변했다

#2은 0~3번 인덱스의 값들이 변했다

#3은 1~4번 인덱스의 값들이 변했다.

 

이때 눈치가 빠른 사람들은 깨달을 수 있다. (1) 배열의 가장 우측에서 시작하여 최초의 오름차순이 생기는 부분부터 변경이 발생한다 (arr[i] < arr[i+1])

하지만 #2와 같이 위의 조건을 만족하는 i가 존재하지 않는다면?! (2) 순열의 가장 마지막 값이므로 첫번째 순열이 다음 순열이다

이제 i부터 그 이후의 원소들을 잘 살펴보자.

#1 [2, 4, 3, 1, 3] -> [1, 3]
#3 [5, 1, 4, 3, 2] -> [1, 4, 3, 2]

#1은 짧으니 #3을 보자. #3의 경우 i를 제외하곤 전부 내림차순으로 정렬돼있다. 그렇다면 (3) i보다 크지만 i에 가장 가까운 수를 찾아서 스왑하면 다음 순열에 한 걸음 더 다가갈 수 있을것 같다. 그리고 i 이후로는 역순으로 정렬돼어 있으므로 가장 우측에서부터 찾으면 된다.

스왑 이후에도 i이후의 원소는 역순으로 정렬된 상태다. 이제 (4) 오름차순으로 정렬하면 끝!

#3 [5, 1, 4, 3, 2] -> [1, 4, 3, 2] -> [2, 4, 3, 1]

 

이 과정에서 코드를 구성할 때 고려해야 하는 부분들을 따로 짚어보자

(1) 배열의 가장 우측에서 시작하여 최초의 오름차순이 생기는 부분부터 변경이 발생한다 (arr[i] < arr[i+1])

(2) 순열의 가장 마지막 값이므로 첫번째 순열이 다음 순열이다

(3) i보다 크지만 i에 가장 가까운 수를 찾아서 스왑

(4) 오름차순으로 정렬

 

위 부분들을 코드로 구현하면 아래와 같다

 

3. 소스 코드

class Solution {
public:
    bool finish = false;

    void nextPermutation(vector<int>& nums) {
        //1. find the first i where nums[i] < nums[i+1] from right
        vector<int> v;
        int len = nums.size();
        int idx = -1;
        for(int i = len-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                idx = i;
                break;
            }
        }
        //2-1. if idx == -1, get first permutation of nums
        if(idx==-1){
            sort(nums.begin(),nums.end());
        }
        //2-2. if idx exists, get index j starting from the right where nums[idx] < nums[j]
        else{
            int j;
            for(int i=len-1;i>idx;i--){
                if(nums[idx] < nums[i]){
                    j = i;
                    break;
                }
            }
            //3. swap nums[idx] and nums[j]
            int temp = nums[idx];
            nums[idx] = nums[j];
            nums[j] = temp;

            //4. reverse nums[idx+1] ~ nums[len-1]
            std::reverse(nums.begin()+idx+1, nums.end());
        }
    }
};