다음 순열

Source: Dev.to

문제 설명

주어진 숫자 배열의 다음 순열을 계산하는 것이 목표입니다.
순열은 같은 원소들의 재배열이며, 다음 순열은 현재 순열보다 사전식으로(lexicographically) 큰 가장 작은 배열을 의미합니다.

알고리즘

1. 뒤에서부터 첫 번째 감소 요소 찾기

오른쪽 끝에서 왼쪽으로 배열을 순회하면서 nums[i] nums[i] 와 같이 처음으로 감소하는 인덱스 i를 찾습니다.

2. i보다 큰 가장 작은 요소 찾기

인덱스 i가 존재한다면, i 오른쪽에 있는 요소 중 nums[i]보다 큰 가장 작은 값을 가진 인덱스 j를 찾습니다.

3. 교환하고 뒤쪽을 뒤집기

nums[i]와 nums[j]를 교환합니다. 그 다음 nums[i + 1:] 부분 배열을 뒤집어 가장 작은 가능한 접미사를 만들고, 이를 통해 다음 순열을 완성합니다.

구현 (Python)

def nextPermutation(nums):
    n = len(nums)
    i = n - 2
    # Step 1: find the first decreasing element
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: find the element just larger than nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # Step 3: swap
        nums[i], nums[j] = nums[j], nums[i]

    # Step 4: reverse the suffix
    nums[i + 1:] = reversed(nums[i + 1:])

예시

nums = [2, 1, 5, 4, 3, 0, 0]
print("Original:", nums)

nextPermutation(nums)
print("Next Permutation:", nums)

출력

Original: [2, 1, 5, 4, 3, 0, 0]
Next Permutation: [2, 3, 0, 0, 1, 4, 5]