BOJ 1517 버블 소트

백준 BOJ 1517 버블 소트 C++

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

 

1) 문제의 N제한이 50만이기 때문에, O(N^2)은 TLE이다. → 문제 이름은 '버블 소트'이지만 "합병 정렬"을 이용하여 풀어야 한다.

2) 합병 정렬 수행시, 원소의 위치가 변경 될 때 그 거리를 count 한다.

3) 합병 정렬을 다시 구현해보고 복습할 수 있는 문제였다.

 

 

// no bubbleSort, yes mergeSort

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int a[500005];
int b[500005];
long long ans=0;

void merge(int start, int mid, int end){

    int i = start;
    int j = mid+1;
    int idx = start;

    // 분할 된 배열의 merge
    while(i<=mid && j<=end){
        if(a[i] <= a[j]) 
            b[idx++] = a[i++];
        else{ // swap point 
            b[idx++] = a[j++];
            ans += (mid - i + 1);
        }
    }

    // 남아 있는 값 일괄 copy
    if(i > mid){
        for(int l=j; l<=end; l++)
            b[idx++] = a[l];
    }
    else{
        for(int l=i; l<=mid; l++)
            b[idx++] = a[l];
    }

    // b->a
    for(int l=start; l<=end; l++)
        a[l] = b[l];
}

void mergeSort(int left, int right){
    int mid = (left+right)/2;

    if(left < right){
        mergeSort(left, mid);
        mergeSort(mid+1, right);
    
        merge(left, mid, right);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> N;
    for(int i=1; i<=N; i++)
        cin >> a[i];
    
    mergeSort(1, N);
    cout << ans;
    
    return 0;
}