[백준] 버블 소트(1517)

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

이 문제는 버블 소트를 진행하는 과정에서 숫자 간의 자리교체(swap)이 몇 번 발생하는 지 카운트하는 문제이다.

데이터의 개수인 N의 최대 범위가 500,000 이므로 $O(nlogn)$의 시간복잡도로 정렬을 수행하면 된다.

이 말은 즉슨 제목은 버블정렬이지만 곧이곧대로 버블정렬을 사용하면 시간복잡도가 $O(N^2)$으로 초과하게 되므로 다른 정렬 기법을 사용하여 swap이 발생하는 개수를 카운트해야 한다.

따라서 우리가 앞서 배운 병합 정렬(Merge Sort)를 이용하여 문제를 해결할 수 있다.

병합 정렬 코드에 대해 제대로 이해하였다면 두 그룹을 병합하는 과정에서 버블정렬의 swap이 포함되어 있다는 것을 떠올릴 수 있다.

(코드 생략 ...)
k = start # k는 병합 정렬에서 정렬된 값을 원본 배열 A에 다시 저장하는 위치 인덱스
idx1 = start # 첫 번째 부분 배열의 시작 인덱스
idx2 = mid + 1 # 두 번째 부분 배열의 시작 인덱스
    
while idx1 <= mid and idx2 <= end:
    # 양쪽 그룹의 index가 가리키는 값을 비교한 후 더 작은 수를 선택해 리스트에 저장한 후
    # 선택된 데이터의 index 값을 오른쪽으로 1칸 이동

        # index1이 가리키는 데이터가 더 큰 경우
        if tmp[idx1] > tmp[idx2]:
            A[k] = tmp[idx2]
            k += 1 # 값을 넣었으니 최종 인덱스도 1칸 이동
            idx2 += 1 # 1칸 이동
            
            # 중요!
            # swap이 발생한 개수 카운트하는 로직 추가 필요!
        
        # index2가 가리키는 데이터가 더 큰 경우
        else:
            A[k] = tmp[idx1]
            k += 1 # 값을 넣었으니 최종 인덱스도 1칸 이동
            idx1 += 1 # 1칸 이동
(코드 생략 ...)

이전에 2751번 문제를 풀면서 병합 정렬을 사용하였는데, 두 그룹을 병합하는 과정에서 index1(idx1)이 가리키는 값이 index2(idx2)이 가리키는 값보다 더 큰 경우 swap이 발생한다.

따라서 2751에서 작성한 코드를 그대로 사용하되, 해당 조건에 부합하는 경우 카운트를 해주면 되는 것이다.

그러면 카운트를 어떻게 해줄 것인가..?

이 질문에 대한 답은 역순쌍이라는 개념을 이해하면 해결할 수 있다.

예를 들어 [3, 5]와 [2]를 병합하는 과정에서 swap이 발생하는 개수를 세고싶다고 가정해보자.

그러면 (3, 2), (5, 2)와 같이 총 2개의 역순쌍이 생기고, 이는 곧 우리가 swap이 발생한 개수를 카운트하는 것과 동일하다.

코드에 주어진 변수에서 k는 병합 정렬에서 정렬된 값을 원본 배열 A에 다시 저장하는 위치 인덱스이고 idx2는 두번째(오른쪽 or 뒤쪽) 배열의 인덱스를 가리키므로 아래와 같은 식이 성립한다.

result += idx2 - k

예제를 대입하면 idx2 - k = 2 - 0 = 2가 되어 역순쌍의 개수, 다시 말해 우리가 구하고자 하는 swap이 발생하는 개수를 정확히 카운트하게 된다.

따라서 문제풀이 코드는 다음과 같다.

import sys
input = sys.stdin.readline

N = int(input())
tmp = [0] * (N)
A = list(map(int, input().split()))
result = 0

def merge_sort(s, e):
    global result
    if e - s < 1: return
    m = int((s + e) / 2)

    merge_sort(s, m)
    merge_sort(m + 1, e)

    for i in range(s, e + 1):
        tmp[i] = A[i]
    
    # 병합 정렬에서 정렬된 값을 원본 배열 A에 다시 저장하는 위치 인덱스
    k = s
    idx1 = s
    idx2 = m + 1

    # e.g. [3, 5]와 [2]를 병합하는 예시를 든다면
    while idx1 <= m and idx2 <= e:
        if tmp[idx1] > tmp[idx2]:
            A[k] = tmp[idx2]
            k += 1
            idx2 += 1

            # e.g. 3 > 2 이므로 역순쌍이 발생하여 idx2(2) - k(0) = 2를 계산한다.
            # 이는 곧 (3, 2), (5, 2)의 2개의 역순쌍을 카운트하는 것과 동일하다.

            # 뒤쪽 데이터 값이 더 작다면 결과값 업데이트
            result += idx2 - k

        else:
            A[k] = tmp[idx1]
            k += 1
            idx1 += 1
    
    while idx1 <= m:
        A[k] = tmp[idx1]
        k += 1
        idx1 += 1
    while idx2 <= e:
        A[k] = tmp[idx2]
        k += 1
        idx2 += 1

merge_sort(0, N - 1)
print(result)