[Leetcode] 31. Next Permutation

Problem

문제 링크

순열을 오름차순으로 나열했을때 주어진 nums의 다음번에 나올 순열을 구하는 문제

Solution

다음으로 큰 순열을 구하기위해서는 가장 작은 단위에서 숫자를 변경하고 그 뒤의 숫자들을 오름차순하는 방법이있다.

1. 가장 작은 단위에서 변경 가능한 숫자를 찾는다. 이유는 순열을 오름차순으로 배치하고 순서를 확인해보면 알 수 있다.
2. left 인덱스의 위치를 찾았다면, left의 오른쪽 배열의 값에서 보다 큰 수를 찾아 swap한다.
3. 마지막으로 left의 오른쪽의 값을들 reverse해주면된다.

std::next_permutation 내부구현

1. a[k] < a[k+1]인 k중 max인 k를 찾는다.
2. a[k]보다 큰 값들 중 m이 가장 큰 m을 찾는다.
3. a[k]와 a[m]을 swap 한다.
4. a[k+1]부터 a[n:전체 사이즈]까지 배열을 reverse한다.

JS Code

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    const swap = (arr, a, b) => [ arr[a], arr[b] ] = [ arr[b], arr[a] ]
    
    let i = nums.length -2
    while(0 <= i && nums[i] >= nums[i+1]) i--
    
    if (0 <= i) {
        let j = nums.length-1
        while(nums[i] >= nums[j]) j--
        swap(nums, i, j)
    }
    nums.push(...nums.splice(i+1).reverse())
};

---

참고

• https://github.com/253eosam/Algorithm/blob/master/algorithm_note/permutation.md
• https://en.cppreference.com/w/cpp/algorithm/next_permutation
• https://hanil0623.tistory.com/2