Next Permutation

Q: 다음 순열의 시간 복잡도는 얼마인가요?

O(n) . 오른쪽에서 한 번 훑어 피벗을 찾고, 두 번째로 교환할 값을 찾은 다음, 한 번 뒤집어 접미부를 바로잡습니다. 모든 작업이 배열 내부에서 이루어지므로 추가 메모리는 O(1) 입니다.

Q: 접미사를 정렬하는 대신 뒤집는 이유는 무엇인가요?

교환 후에도 접미부는 여전히 내림차순이므로, 이를 뒤집기만 해도 이미 오름차순으로 정렬됩니다. 뒤집기에는 O(n) 이 걸리고, 정렬해도 같은 결과를 얻지만 O(n log n) 이 걸립니다.

Q: Next Permutation은 중복 값과 함께 작동하나요?

네, 두 비교 모두 같은 값을 더 크지 않은 것으로 취급하는 한 그렇습니다. 피벗 검색은 ≥ 를 사용해 같은 이웃 값을 건너뛰고, 교환 검색은 ≤ 를 사용해 피벗과 같은 값을 건너뜁니다. 그러면 [1, 5, 1] 은 다음으로 구별되는 배열인 [5, 1, 1] 이 됩니다.

보통배열과 문자열 투 포인터

+10

정수 배열 nums가 주어지며, 값은 반복될 수 있습니다. 이 값들의 서로 다른 모든 배열을 사전 순서로 정렬한다고 생각해 보세요. 두 배열이 처음으로 달라지는 인덱스에서 비교하여, 그 위치의 값이 더 작은 배열이 먼저 옵니다. 이 순서에서 nums 바로 다음에 오는 배열을 반환하세요.

nums가 이미 가장 큰 배열이라면 그다음 배열은 없습니다. 가장 작은 배열, 즉 값을 오름차순으로 정렬한 배열을 반환하세요. O(n) 시간과 O(1) 추가 메모리를 목표로 하세요.

함수

nextPermutation(nums: integer-array) → integer-array

numsinteger-array: 현재 값의 배치
반환값integer-array: 사전식 순서에서 다음 배열이거나, nums가 가장 큰 경우 오름차순으로 정렬된 값

제약 조건

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

예제

입력: nums = [2, 5, 4, 1]
출력: [4, 1, 2, 5]
설명: 꼬리 5, 4, 1가 감소하고 있으므로, 그 앞의 2는 커져야 합니다. 2보다 큰 꼬리 값 중 가장 작은 값은 4입니다. 그 자리에 2를 넣고 나머지는 오름차순으로 정렬합니다: [4, 1, 2, 5].

입력: nums = [3, 2, 2, 1]
출력: [1, 2, 2, 3]
설명: 배열 전체가 감소하고 있으므로, 이는 3, 2, 2, 1의 가장 큰 배열입니다. 답은 가장 작은 배열인 [1, 2, 2, 3]으로 순환합니다.

입력: nums = [1, 5, 1]
출력: [5, 1, 1]
설명: 첫 번째 1은 커져야 합니다. 마지막 1은 첫 번째 1과 같고 더 크지 않으므로, 그 자리에 올 수 있는 유일한 값은 5이며, 따라서 [5, 1, 1]이 됩니다.

후속 질문

대신 이전 순열, 즉 사전순으로 nums 바로 앞에 오는 순열은 어떻게 찾을 수 있을까요?

풀이

내림차순 접미부는 그 값들이 허용하는 최대 크기이므로, 다음 배열 순서는 그 바로 앞의 값인 피벗을 바꿉니다. 피벗을 가능한 한 조금 증가시킨 다음 접미부를 가능한 한 작게 만듭니다. 이를 위해 오른쪽에서 두 번 훑고 배열 안에서 한 번 뒤집습니다.

목록을 순서대로 정렬하기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

정렬된 값으로부터 깊이 우선 방식으로 배열을 만들고, 사용하지 않은 값 중 가장 작은 값부터 항상 시도합니다. 이렇게 하면 사전순으로 만들어지므로 nums보다 엄격하게 큰 첫 번째 배열이 정답입니다. 그런 배열이 없다면 정렬된 값을 반환합니다. 중복된 값이 있으면 [1, 1, 5]의 경우 115, 151, 115, 151, 511, 511처럼 일부 배열이 두 번 만들어지지만, 복사본은 앞서 만든 배열만 반복하므로 처음으로 큰 배열은 여전히 다음 배열입니다.

개수는 n!만큼 증가합니다. 서로 다른 값이 12개라면 배열은 479,001,600개입니다.

알고리즘

nums의 복사본을 정렬하여 pool에 저장합니다.
pool에서 사용하지 않은 항목을 왼쪽에서 오른쪽으로 선택해 깊이 우선으로 배열을 구성합니다.
배열이 완성되면 위치별로 nums와 비교합니다.
nums보다 큰 첫 번째 배열을 반환합니다.
더 큰 배열이 없으면 pool을 반환합니다.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

피벗을 찾고, 교환한 다음, 접미부를 뒤집습니다

핵심 아이디어

피벗은 오른쪽에서부터 찾았을 때 오른쪽 이웃보다 작은 첫 번째 값입니다. [2, 5, 4, 1]에서는 2입니다. 이 값은 증가시킬 수 있는 가장 오른쪽 위치이며, 가능한 가장 오른쪽 위치를 증가시키면 증가 폭이 가장 작아집니다.

피벗보다 엄격하게 큰 접미부 값 중 가장 작은 값과 피벗을 바꿉니다. 접미부는 내림차순이므로, 피벗보다 큰 값 중 가장 오른쪽에 있는 값인 4와 바꾸면 [4, 5, 2, 1]이 됩니다. 이전 피벗이 4가 있던 자리에 들어맞으므로 접미부는 여전히 내림차순입니다. 앞부분이 이제 더 커졌으므로 접미부는 가능한 한 작아야 하며, 오름차순이어야 합니다. 내림차순으로 이어진 구간을 뒤집으면 이렇게 됩니다: [4, 1, 2, 5].

피벗이 없으면 배열은 가장 큰 순열이며, 전체를 뒤집으면 가장 작은 순열이 됩니다. 각 단계는 한 번의 탐색 또는 한 번의 뒤집기이므로 시간 복잡도는 O(n)이고 메모리 복잡도는 O(1)입니다. 다만 R 버전은 O(n) 크기의 복사본을 반환합니다.

알고리즘

i를 n-2로 설정하고 nums[i] ≥ nums[i + 1]인 동안 왼쪽으로 이동시킵니다.
i ≥ 0이면 j를 n-1로 설정하고 nums[j] ≤ nums[i]인 동안 왼쪽으로 이동시킨 다음, nums[i]와 nums[j]를 바꿉니다.
서로를 향해 이동하는 두 인덱스를 사용해 i + 1부터 끝까지의 부분을 뒤집습니다.
nums를 반환합니다.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

함정과 경계 사례

피벗을 찾을 때 ≥ 대신 >를 사용하는 경우. [3, 2, 2, 1]에서 2, 2 쌍은 오름차순이 아니며, 거기서 멈추면 더 커질 수 없는 피벗을 선택하게 됩니다.
피벗과 같은 값과 교환하는 경우. [1, 5, 1]에서 두 1을 교환해도 달라지는 것이 없습니다. 엄밀히 더 큰 값을 찾으세요.
접미부에서 가장 큰 값과 교환하는 경우. [2, 5, 4, 1]에서는 5가 앞에 오므로 4로 시작하는 모든 배열을 건너뛰게 됩니다.
피벗이 없는 경우를 건너뛰는 경우. 가장 큰 배열은 전체 배열을 뒤집어 정렬된 상태로 되돌려야 합니다.
Rust에서 n-2부터 시작하는 usize 인덱스는 n = 1일 때 패닉을 일으키며, 피벗이 없을 때 0을 지나 왼쪽으로 이동해도 패닉을 일으킵니다. 부호 있는 인덱스를 사용하거나 1부터 세세요.

자주 묻는 질문3

다음 순열의 시간 복잡도는 얼마인가요?

O(n). 오른쪽에서 한 번 훑어 피벗을 찾고, 두 번째로 교환할 값을 찾은 다음, 한 번 뒤집어 접미부를 바로잡습니다. 모든 작업이 배열 내부에서 이루어지므로 추가 메모리는 O(1)입니다.

접미사를 정렬하는 대신 뒤집는 이유는 무엇인가요?

교환 후에도 접미부는 여전히 내림차순이므로, 이를 뒤집기만 해도 이미 오름차순으로 정렬됩니다. 뒤집기에는 O(n)이 걸리고, 정렬해도 같은 결과를 얻지만 O(n log n)이 걸립니다.

Next Permutation은 중복 값과 함께 작동하나요?

네, 두 비교 모두 같은 값을 더 크지 않은 것으로 취급하는 한 그렇습니다. 피벗 검색은 ≥를 사용해 같은 이웃 값을 건너뛰고, 교환 검색은 ≤를 사용해 피벗과 같은 값을 건너뜁니다. 그러면 [1, 5, 1]은 다음으로 구별되는 배열인 [5, 1, 1]이 됩니다.

def nextPermutation(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [2, 5, 4, 1]

예상 출력

[4, 1, 2, 5]