[Leetcode] 31. Next Permutation 문제 풀이

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

Next Permutation - LeetCode

문제 내용

배열이 주어지는 데 해당 배열에서 사전순으로 생각했을 때

다음 Permutation을 출력하는 문제

 

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

문제 풀이

다음 Permutation을 생각했을 때 특징이 있었다.

오른쪽에서 왼쪽으로 갈 때 숫자가 점점 증가하는 부분이다.

만약 감소하는 부분을 만나면 거기가 경계선이 된다.

예를 들어 2진수 0111에서 1000 이 되는 0|1 같은 경계선이다.

해당 경계선에 대해 swap하고 reverse 하면 다음 Permutation을 찾을 수 있다.

 

먼저 경계선 index인 i를 찾고,  i-1 과 i 가 경계선이다.

swap하는 숫자를 찾아야 하는데

그 숫자는 경계선인 i-1 에 대해 다음으로 큰 수 이다.

즉, i~size-1 까지 범위 중에 i-1보다 크지만 범위 안에서는 최소인 값을 찾아야 한다.

코드

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