[ LeetCode ][JAVA][31] Next Permutation (다음 순열)

leetcode.com/problems/next-permutation/

Next Permutation - LeetCode

문제

Implementnext permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must bein-placeand use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

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

 

해석하자면, 주어진 배열의 다음 순열을 구하라!

접근

1. 렉시컬 소트를 아는가?
2. 추가 메모리 사용하지 않고 스왑할 수 있는가?
3. 다시 되돌아 오는 예외상황을 이해하는가?
   로 볼 수 있다.

문제를 풀기위한 순서는 이렇게 가정했다.

1. 뒤에서부터 탐색하면서 오름차순이 깨지는 인덱스를 확인(a)
2. 다시 뒤에서부터 암색하면서 1에서 구한것보다 큰 첫번째 인덱스를 확인(b)
3. a랑 b를 스왑
4. a+1에서부터 끝까지 오름차순정렬

코드

class Solution{
    /*
    1 3(a) 5 4 4(b)
    ->
    1 4 3 4 5
    
    5 4 3 2 1
    
    1. 렉시컬 소트를 아는가 ?
    2. 추가 메모리 사용하지 않고 스왑할 수 있는가
    3. 다시 디ㅗ돌아오는 예외상황을 이해하는가
    */
    public void nextPermutation(int[] nums){
        // 뒤에서부터 탐색하면서 오름차순이  깨지는 인덱스를 확인(a)
        int a = nums.length-2;
        while(a>=0 && nums[a] >= nums[a+1]) a--;
        
        if(a != -1){
            // 다시 뒤에서부터 탐색하면서 a보다 큰 첫번째 인덱스를 확인(b)
            int b = nums.length-1;               
            while(nums[a] >= nums[b]) b--;
            // a랑 b를 스왑
            swap(nums, a, b);
        }
        // a+1에서부터 끝까지 오름차순 정렬
        int start = a + 1;
        int end = nums.length - 1;
        while(start < end){
            swap(nums, start++, end--);
        }
    }
    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}