[LeetCode] 31. Next Permutation

문제 설명

문제 풀이

시간 복잡도 : O(N!) / 공간 복잡도 : O(N)

아래와 같은 기존의 next_permutation 알고리즘을 이용하되 마지막 순열에서 넘어갈 때 조건 설정을 추가해주었다.

1. list(수열)에 대해서 list[i-1] < list[i]를 만족하는 가장 큰 수를 찾는다. 
2. 1번에서 찾은 i-1에 대하여 list[i-1] < list[j]를 만족하는 가장 큰 j를 찾는다.
3. list[i-1], list[j]를 swap한다. 
4. list[i ... n-1]을 reverse 시킨다. 

소스 코드 (JAVA)

class Solution {
    public void reverse(int[] nums,int i,int n){
        for(;i<n;) swap(nums, i++, n--); 
    }
    
    public void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
    
    public void nextPermutation(int[] nums) {
        int i, j;
        i = j = nums.length - 1;
        if (i == 0) return;
        while(nums[i-1] >= nums[i]) {
            if (--i == 0) {
                Arrays.sort(nums);
                return;
            }
        }
        while(nums[j] <= nums[i-1]) { 
            if(--j == 0) { 
                Arrays.sort(nums);
                return;
            }
        }
        swap(nums, j, i-1);
        reverse(nums, i, nums.length-1);
    }
}