문제

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

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

The replacement must be in place and use only constant extra memory.

제한사항

• 1 $\leq$ nums.length $\leq$ 100
• 0 $\leq$ nums[i] $\leq$ 100

접근

순열 알고리즘에서 주어진 배열의 다음 순열을 찾는 문제였어요. 이번엔 새로운 알고리즘을 배운다는 느낌으로 접근했어요. 다음 순열 알고리즘을 구하는 방법은,

1. 역순으로 검색해 오름차순으로 정렬된 인접 원소의 첫 번째 인덱스를 찾는다 $\to$ i
2. 역순으로 검색해 i보다 큰 원소의 인덱스를 찾는다 $\to$ j
3. i와 j swap
4. i+1부터의 원소들 reverse

이렇게 하면 다음 순열을 찾는 알고리즘이 완성됩니다.

답안

class Solution {
    public void nextPermutation(int[] nums) {
        // 1. 역순으로 검색해 최초의 인접 원소의 오름차순 위치를 찾습니다.
        int i = nums.length - 2;
        while((i >= 0) && nums[i] >= nums[i + 1]){
            --i;
        }

        if(0 <= i){
            // 2. 역순으로 검색해 i번째 원소보다 큰 값을 찾음
            int j = nums.length - 1;
            while(nums[i] >= nums[j]){
                --j;
            }
            swap(nums, i, j);
        }
        // 3. 마지막으로 i + 1부분부터 역전
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start){
        int i = start;
        int j = nums.length - 1;
        while(i < j){
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
}

후기

아직까지 배워야할 것이 많이 남았음을 느꼈습니다. 그리고 LeetCode를 몇번 하고 나니 느낀건, 조만간 이거 가지고 응용 문제 나오겠구나...였네요 ㅋㅋ 지금 내용을 반드시 숙지해야 함을 느꼈습니다.