BOJ 1517 버블 소트

www.acmicpc.net/problem/1517

1517번: 버블 소트

 

버블 소트를 하면서 스왑하는 개수가 총 몇 번 나오는지 확인하면 되는데 

N이 50만이라 버블 소트를 사용해서 해결하면 TLE가 난다.

\(O(NlogN)\)으로 해결해야 하는데 퀵 소트나 머지 소트를 사용해서 약간 응용시켜주면 된다.

 

우선 기존 병합 정렬에서 원소를 각 하나씩 남을 때까지 쪼개주고,

 

 

void mergeSort(int* ar, int s, int e) {
    if (s < e) {
        mergeSort(ar, s, (s + e) / 2);
        mergeSort(ar, (s + e) / 2 + 1, e);
        merge(ar, s, (s + e) / 2, e);
    }
}

 

기존 병합 정렬이랑 똑같이 해결해주면 되는데 이때 병합하는 과정에서 교차가 일어날 때마다 

카운팅해주면 된다.

 

 

사진처럼 오른쪽에서 병합되면 cnt + 1 왼쪽에서 병합되면 ans += cnt

식으로 병합해주면 된다.

 

 

#include <iostream>
using namespace std;
 
int tmp[500001], ar[500001];
long long ans, cnt, n;
 
void merge(int* ar, int s, int mid, int e) {
    int i = s, j = mid + 1, k = s;
    cnt = 0;
    while (i <= mid || j <= e) {
        if (i > mid) cnt++, tmp[k++] = ar[j++];
        else if (j > e) ans += cnt, tmp[k++] = ar[i++];
        else if (ar[i] <= ar[j]) ans += cnt, tmp[k++] = ar[i++];
        else cnt++, tmp[k++] = ar[j++];
    }
    for (int i = s; i <= e; ++i) ar[i] = tmp[i];
}
 
void mergeSort(int* ar, int s, int e) {
    if (s < e) {
        mergeSort(ar, s, (s + e) / 2);
        mergeSort(ar, (s + e) / 2 + 1, e);
        merge(ar, s, (s + e) / 2, e);
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> ar[i];
 
    mergeSort(ar, 0, n - 1);
 
    cout << ans << endl;
 
    return 0;
}