[BOJ] 1517번 버블 소트 (C++) [Do it!]

문제

https://www.acmicpc.net/problem/1517

풀이

N이 최대 500,000이므로 $O(N^2)$으로 풀 수 없다는 사실을 알 수 있다. 따라서 $O(N)$ 혹은 $O(Nlog(N))$으로 풀어야 할 것 같은데 고민을 해도 접근 방법이 떠오르지 않아 풀이를 찾았다.

그 결과 Inversion Counting이라는 개념을 알게 되었다. 이는 역순으로 되어 있는 순서쌍의 개수를 세는 알고리즘이고, 이는 버블 정렬을 진행할 때 몇 번이나 교환을 진행하는지의 숫자와 같다.

이때 Inversion Counting 을 구하는 방법은 2가지이다.
1) Segment Tree 응용
2) Merge Sort 응용

1. Segment Tree를 이용하여 구간합 관리

• Segment Tree란?
  -> 구간 중에 Max,Min,Sum(최대,최소,구간의 합) 등을 빠르게 갱신할 수 있는 자료구조

2. Merge Sort 응용

정렬된 결과와의 교차점의 개수는 Inversion된 쌍의 수와 같다.

(출처: https://medium.com/@ssbothwell/counting-inversions-with-merge-sort-4d9910dc95f0)

이때, 교차점의 개수를 구하는 방법은 Merge Sort 과정을 통해 구할 수 있다.

(출처: https://koder.page/230)

def mergeSortInversions(arr):
    if len(arr) == 1:
        return arr, 0

    left_arr = arr[len(arr) / 2:]
    right_arr = arr[:len(arr) / 2]

    left_arr, left_inversion_cnt = mergeSortInversions(left_arr)
    right_arr, right_inversion_cnt = mergeSortInversions(right_arr)

    inversion_cnt = left_inversion_cnt + right_inversion_cnt

    # !핵심 파트
    merged_arr = []
    left_idx = 0
    right_idx = 0

    while left_idx < len(left_arr) and right_idx < len(right_arr):
        if left_arr[left_idx] >= right_arr[right_idx]:  # 교차점 생성 X
            merged_arr.append(right_arr[right_idx])
            right_idx += 1
        else:
            merged_arr.append(left_arr[left_idx])
            left_idx += 1
            inversion_cnt += (len(right_arr) - right_idx)  # 남아있는 원소들은 다 교차점 생성

    # 위 while문 이후에 남은 값들 더해주기
    merged_arr += left_arr[left_idx:]
    merged_arr += right_arr[right_idx:]

    return merged_arr, inversion_cnt