LeetCode Next Permutaion (JavaScript), 순열

링크 : https://leetcode.com/problems/next-permutation/solutions/6750829/video-dont-worry-if-you-cant-solve-this-75qi1/

문제 설명

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

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

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

---

문제 풀이

순열을 구하는 공식

1. 오른쪽 -> 왼쪽으로 오름차순이 깨지는 순간 찾기 (array[index] < array[index + 1]인 순간의 index 찾기)

2. 1번에서 구한 index 오른쪽 부분에서 array[index] 값보다 큰 값 중 가장 작은 값 찾기

3. 1번에서 구한 값과 2번에서 구한 값을 swap

4. 순열로 유지하기위해 index 우측 부분을 역순으로 정렬 (역순으로 정렬하는 이유는 뒷 부부을 가장 작은 오름차순으로 유지하기 위해)

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    const reverse = (start) => {
        let i = start;
        let j = nums.length - 1;
        while (i < j) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
            j--;
        }
    }

    // 1. 오른쪽 -> 왼쪽 오름차순이 깨지는 index 찾기
    let pivot = -1;
    for (let i = nums.length - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) {
            pivot = i;
            break;
        }
    }

    if (pivot === -1) {
        reverse(0);
        return nums;
    }

    // 2. index + 1 ~ 끝, swap할 대상 찾기 nums[index] 보다 크면서 가장 작은 값
    let swap = -1;
    for (let i = nums.length - 1; i > pivot; i--) {
        if (nums[i] > nums[pivot]) {
            swap = i;
            break; // 오른쪽에서 만나는 첫 번째가 가장 작은 값
        }
    }

    // 3. swap
    [nums[pivot], nums[swap]] = [nums[swap], nums[pivot]];
    
    // 4. index + 1 부분 역순 정렬 -> 뒷 부분이 가장 작은(오름차순)으로 정렬
    reverse(pivot + 1);

    return nums;
};

---

결론

순열을 구하는 방식을 알아야 함

https://www.youtube.com/watch?v=BbJ3vlrEAH0&t=362s