[LeetCode] 31. Next Permutation

순열의 사전식 다음 순열을 알아내는 절차와 알고리즘이 있다는 것을 알게되었음

1. 순열 요소의 우측 끝부터 왼쪽 방향으로 이동하며 첫 번째로 감소하는 원소 찾기
   1-1. 예: [1,3,5,4,2]에서 3이 그 지점 (5 > 3). i로 지칭
2. nums[i] 보다 큰 가장 작은 요소 찾기 (다음으로 큰 순열을 만들기 위해 교체할 가장 작은 수를 찾는 과정) j로 지칭
3. nums[i]와 nums[j]요소 교환
4. 교환 후 i+1번째 부터 끝 요소까지 뒤집기(reverse)

😎풀이

function nextPermutation(nums: number[]): void {
    // 배열의 길이를 구합니다.
    const n = nums.length;
    
    // 1. 오른쪽에서부터 왼쪽으로 이동하면서 첫 번째로 감소하는 원소 찾기.
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) {
        // 2. i 이후의 숫자 중 nums[i]보다 큰 가장 작은 숫자 찾기
        let j = n - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        
        // 3. nums[i]와 nums[j] 교환
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    
    // 4. i+1부터 모든 부분 배열 뒤집기
    reverse(nums, i + 1);
}

// 배열의 일부를 뒤집는 헬퍼 함수
function reverse(nums: number[], start: number): void {
    let left = start;
    let right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}