[leetcode] Next Permutation

유의할점

순열의 끝

풀이

순열의 끝은 모든 수가 역순일 때이다. 예를 들면

1 2 5 4 3 에서 2 5 4 3은 2로 시작되는 순열의 끝이라고 할수있다.

2는 교체되어야 할것이다. 2보다 작은 수로 교체될수는없다. → 이전 permutation

즉 2의 바로 직후의 큰수를 구한뒤 교체한다. 교체된 수열의 처음은 오름차순 정렬이 될것이므로. 정렬한다. → 1 3 2 4 5

upper_bound를 위해서 정렬된 부분수열이 필요하므로 정렬후, upper_bound를 실행했다.

코드

C++

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int cur = nums.size();        
        while(cur--){
            if(cur==0){
                sort(nums.begin(),nums.end());
                return;
            }
                
            
            int &beforeValue = nums[cur-1];
            int &currentValue = nums[cur];
            
            if(beforeValue < currentValue){
                sort(nums.begin()+cur,nums.end());
                int changedIdx = upper_bound(nums.begin()+cur,nums.end(),nums[cur-1]) - nums.begin();
                swap(nums[cur-1],nums[changedIdx]);
                return;
            }
        }
        
    }
};