BOJ 1517 - 버블 소트

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

Bubble Sort를 실행할시 수행되는 Swap의 횟수를 출력하는 프로그램을 작성하라

Solution

일반적으로 Bubble Sort를 실행해서 횟수를 세는 방법도 있겠지만 기본적으로 시간복잡도가 O(N^2) 이기에 문제의 조건을 맞추지 못하고 시간초과가 나버린다.

그렇기에 이 문제는 Inversion counting 방법을 사용해야하는데, 프로그래밍에서 Inversion은 A[i] > A[j] (i<j) 일때를 의미한다.

예를들어 3 1 2 값이 주어졌을때 Inversion 의 개수는

{3 1, 3 2} 로 총 2개가 존재한다. 쉽게 생각해서 앞서있는 숫자가 현재 위치의 숫자보다 클시 Inversion하다고 말한다.

Bubble Sort의 Swap횟수 또한 자신의 뒤에 작은숫자의 개수와 같기때문에 위와 같은 방법을 사용할 수 있다.
(3 1 2 를 정렬시 3 1 swap, 3 2 swap -> 총 2번 일어남)

Inversion의 개수는 MergeSort를 활용해서 해결할 수 있는데

1	5		2	3

1 5배열과 2 3 배열을 merge하는 상황이라고 가정해보자.

2 3(오른쪽) 배열이 새로 정렬되는 배열에 들어갈시 1 5(왼쪽) 배열의 원소의 개수가 Inversion의 개수가 된다.

상세히 적어보자면 우선 1이 가장먼저 정렬될것이다. 이후에는 오른쪽 배열에 있는 2가 정렬될것인데 이 때 왼쪽 배열에 원소5, 1개가 존재한다. 이 때 Inversion이 1개가 추가된다는 뜻이고, 이후에 3이 정렬될때도 왼쪽 배열에 여전히 원소가 1개 남아있으므로 (5) 총 Inversion의 개수는 2개가 된다.

이와 같이 합병할때마다 Inversion count를 해주면 정답을 구할 수 있다.

Merge Sort에서 단 한줄의 추가로만 해결가능!

Code

#include <bits/stdc++.h>
using namespace std;
#define MAXV 500001

int n;
int a[MAXV];
int b[MAXV];
long long ans;

void merge(int start, int end) {
    int mid = (start + end) / 2;
    int i = start;
    int j = mid + 1;
    int k = 0;

    while (i <= mid && j <= end) {
        if (a[i] <= a[j]) 
            b[k++] = a[i++];
        else {
            b[k++] = a[j++];
            ans += (long long)(mid - i + 1); //왼쪽 원소의 개수 = Inversion 개수 
        }
    }
    
    while (i <= mid) b[k++] = a[i++];
    while (j <= end) b[k++] = a[j++];

    for (int i = start; i <= end; i++)
        a[i] = b[i - start];

}

void mergesort(int start, int end) {
    if (start >= end) return;
    
    int mid = (start + end) / 2;

    mergesort(start, mid);
    mergesort(mid + 1, end);
    merge(start, end);

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];

    mergesort(0, n - 1);

    cout << ans << '\n';

    return 0;
}

참고 : https://code.plus/course/43 , 분할 정복(연습)