Count Inversions

Q: 배열에서 역전이란 무엇인가요?

역전은 i < j 인 위치 쌍으로, nums[i] > nums[j] 인 경우를 말합니다. 즉, 더 큰 값이 더 작은 값보다 앞에 놓여 있습니다. 정렬된 리스트에는 역전이 0개 있고, 서로 다른 값들로 이루어진 역순 리스트에는 가장 많은 n(n-1)/2 개의 역전이 있습니다. 역전의 개수는 버블 정렬이 수행하는 인접한 원소 간 교환 횟수와 같습니다.

Q: 병합 정렬을 사용해 역전 쌍을 세는 시간 복잡도는 얼마인가요?

O(n log n) 시간 복잡도와 병합 버퍼를 위한 O(n) 추가 공간이 필요합니다. 병합의 각 log n 단계에서 모든 값을 한 번씩 처리하므로, 2 × 10^4 개의 값에 대해 약 3 × 10^5 단계가 필요합니다. 쌍별로 처리하는 루프는 O(n²) 입니다.

보통정렬 재귀

+10

정수 목록 nums가 주어졌을 때, 역전의 개수를 반환하세요. 역전은 i < j이고 nums[i] > nums[j]인 인덱스 쌍으로, 더 큰 값이 더 작은 값보다 앞에 있는 경우입니다. 같은 값끼리는 역전을 이루지 않으며, 정렬된 목록에는 역전이 없습니다.

함수

countInversions(nums: integer-array) → integer

numsinteger-array: 정수 목록
반환값integer: nums[i] > nums[j]인 i < j 쌍의 개수

제약 조건

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
답은 최대 n(n-1)/2 < 2 × 10⁸이므로 부호 있는 32비트 정수에 들어갑니다.

예제

입력: nums = [5, 3, 8, 1, 4]
출력: 6
설명: 5는 3, 1, 4보다 앞에 있습니다: 3쌍입니다. 3은 1보다 앞에 있고, 8은 1과 4보다 앞에 있습니다: 3쌍이 더 있습니다. 1과 4는 순서가 맞으므로 합계는 6입니다.

후속 질문

nums[i] > 2 × nums[j]일 때만 쌍으로 세면 무엇이 달라질까요? 병합 정렬로 여전히 O(n log n)에 이러한 쌍을 셀 수 있을까요?

풀이

모든 쌍을 확인하면 약 n² / 2번 비교하게 됩니다. 병합 정렬은 쌍을 한꺼번에 셉니다. 병합 중 오른쪽 절반의 값이 배치될 때, 아직 대기 중인 왼쪽의 모든 값은 그보다 크고 앞에 있었습니다. 한 번의 뺄셈으로 이 전체 묶음을 셀 수 있으므로, 계산에는 O(n log n) 정렬 외의 추가 비용이 들지 않습니다.

모든 쌍을 확인하세요

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

핵심 아이디어

모든 인덱스 i에 대해 그 뒤에 오는 모든 인덱스 j를 확인하고 nums[i] > nums[j]일 때 1을 더합니다. 이것이 정의이며, 엄격한 비교이므로 값이 같은 경우는 제외됩니다.

비교 횟수는 n(n-1)/2입니다. 값이 2 × 10^4개일 때 거의 2 × 10^8번이고, n을 두 배로 늘리면 비교 횟수는 네 배가 됩니다.

알고리즘

count = 0으로 설정합니다.
0부터 n-1까지의 각 i와 i + 1부터 n-1까지의 각 j에 대해, nums[i] > nums[j]일 때 count에 1을 더합니다.
count를 반환합니다.

def countInversions(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                count += 1
    return count

병합하면서 개수를 세는 병합 정렬

핵심 아이디어

리스트를 중간에서 나눕니다. 역전 쌍은 두 값 모두 왼쪽 절반에 있거나, 둘 다 오른쪽 절반에 있거나, 하나씩 양쪽에 있습니다. 각 절반에 재귀적으로 적용하면 앞의 두 종류를 세고 해당 절반을 정렬합니다. 정렬은 각 절반 안에서만 값을 이동하므로 왼쪽의 모든 값은 여전히 오른쪽의 모든 값보다 앞에 오며, 양쪽 절반에 걸친 쌍은 바뀌지 않습니다.

병합할 때 left[i] ≤ right[j]이면 left[i]를 놓습니다. 아직 남아 있는 오른쪽 값은 모두 right[j] 이상이므로 역전 쌍을 만들지 않습니다. 그렇지 않으면 right[j]가 left[i]보다 작고, 왼쪽 절반이 정렬되어 있으므로 아직 남아 있는 왼쪽 값 모두보다 작습니다. 그 개수를 더합니다. 값이 같을 때는 왼쪽 값을 먼저 놓아 같은 값끼리 역전 쌍이 생기지 않게 합니다.

[5, 3, 8, 1, 4]에서는 각 절반에 역전 쌍이 각각 1개와 2개 있습니다. [3, 5]와 [1, 4, 8]을 병합할 때 1은 3과 5를 지나고, 4는 5를 지나므로 1 + 2 + 3 = 6입니다.

알고리즘

nums를 복사하고 같은 길이의 버퍼를 만드세요.
값이 2개 미만인 범위를 정렬하고 세려면 0을 반환하세요.
그렇지 않으면 mid에서 분할하고 각 절반을 정렬하고 세세요.
버퍼를 통해 두 절반을 병합하세요. left[i] ≤ right[j]이면 왼쪽 값을 가져오고, 그렇지 않으면 오른쪽 값을 가져온 다음 아직 배치하지 않은 왼쪽 값의 개수를 더하세요.
병합된 범위를 다시 복사하고 세 개의 개수를 더한 값을 반환하세요.

def sortAndCount(a, buf, lo, hi):
    # Sorts a[lo:hi] and returns the number of inversions inside it.
    if hi - lo < 2:
        return 0
    mid = (lo + hi) // 2
    count = sortAndCount(a, buf, lo, mid) + sortAndCount(a, buf, mid, hi)
    # Merge the two sorted halves, counting the pairs that cross the middle.
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[i] <= a[j]:
            buf[k] = a[i]
            i += 1
        else:
            # a[j] is smaller than every left value not placed yet: a[i..mid-1].
            buf[k] = a[j]
            j += 1
            count += mid - i
        k += 1
    while i < mid:
        buf[k] = a[i]
        i += 1
        k += 1
    while j < hi:
        buf[k] = a[j]
        j += 1
        k += 1
    a[lo:hi] = buf[lo:hi]
    return count


def countInversions(nums):
    a = list(nums)  # sort a copy, not the caller's list
    return sortAndCount(a, [0] * len(a), 0, len(a))

함정과 경계 사례

오른쪽 값이 배치될 때 1을 더합니다. 아직 대기 중인 모든 왼쪽 값을 지나치므로 그 개수인 mid - i를 더합니다.
동점일 때 오른쪽 값을 선택하고 왼쪽을 선택하는 조건으로 left[i] < right[j]를 사용합니다. 그러면 [2, 2, 2, 1]에서 같은 2끼리 서로 비교되어 3보다 큰 값이 반환됩니다. ≤를 사용하세요.
한쪽 절반이 바닥난 후 남은 값을 복사하는 동안 개수를 셉니다. 남은 왼쪽 값 뒤에는 오른쪽 값이 없고, 남은 오른쪽 값은 이미 모든 왼쪽 값과 비교되었습니다.

자주 묻는 질문3

배열에서 역전이란 무엇인가요?

역전은 i < j인 위치 쌍으로, nums[i] > nums[j]인 경우를 말합니다. 즉, 더 큰 값이 더 작은 값보다 앞에 놓여 있습니다. 정렬된 리스트에는 역전이 0개 있고, 서로 다른 값들로 이루어진 역순 리스트에는 가장 많은 n(n-1)/2개의 역전이 있습니다. 역전의 개수는 버블 정렬이 수행하는 인접한 원소 간 교환 횟수와 같습니다.

병합 정렬을 사용해 역전 쌍을 세는 시간 복잡도는 얼마인가요?

O(n log n) 시간 복잡도와 병합 버퍼를 위한 O(n) 추가 공간이 필요합니다. 병합의 각 log n 단계에서 모든 값을 한 번씩 처리하므로, 2 × 10^4개의 값에 대해 약 3 × 10^5단계가 필요합니다. 쌍별로 처리하는 루프는 O(n²)입니다.

병합 정렬 없이 역전 쌍을 셀 수 있을까요?

네. 값의 순위에 대한 펜윅 트리(이진 인덱스 트리)는 목록을 한 번 순회하면서 각 값에 대해 이전 값 중 더 큰 값이 몇 개인지 O(log n)의 시간에 확인합니다. 전체적으로도 O(n log n)입니다. 서브트리 크기를 추적하는 균형 검색 트리도 같은 방식으로 작동합니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

nums = [5, 3, 8, 1, 4]

예상 출력