BOJ 1517 버블 소트

문제

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

버블 소트에서 발생하는 swap 의 수를 세는 문제이다.

 

풀이

결론부터 말하자면 inversion 들의 수를 세는 문제라고 할 수 있다.

 

버블 소트의 특징 중에는 한번 포문을 돌 때마다 젤 큰 수가 마지막으로 옮겨 간다는 성질이 있다.

이를 이용해, 잘 생각해 보면 swap 의 수는 배열 안의 각 수에 대하여 그 수보다 오른쪽에 있는 수들 중 그 수보다 작은 수들의 개수라 할 수 있다.

아직 $O(N^2)$ 이니, 조금 더 개선 해 보자.

 

일단 히스토그램 문제처럼, $(s, e)$ 구간을 $(s, mid)$, $(mid+1, e)$ 구간으로 나눌 수 있다.

그럼 재귀적으로 다 해결되고, $(s, mid)$ 의 구간의 각 수에 대하여 $(mid+1, e)$ 의 구간에 자기보다 작은 수들을 세면 문제는 풀린다.

 

단순하게 생각해서 $(mid+1, e)$ 구간을 모두 정렬한 후 $(s, mid)$ 에 대하여 lower_bound 를 돌려도 $O(Nlog^2N)$으로 풀 수는 있다.

하지만 $O(NlogN)$ 풀이를 보자.

 

위 풀이와 비슷하게 하고, conquer 과정을 $O(N)$ 안에 풀면 된다.

바로 머지 소트이다.

왼쪽 배열의 각 수를 합쳐 나갈 때마다, 오른쪽 배열 에서는 얼마나 들어가 있는지를 세면 그것이 곧 자신보다 작은 수의 개수이다.

 

시간복잡도 : $O(NlogN)$

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

typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 500000

int n, arr[MAXN+10];
ll ans;

void solve(int s, int e)
{
    if(s==e) return;

    int mid=(s+e)/2;
    solve(s, mid);
    solve(mid+1, e);

    int i, j;
    vector<int> t;

    for(i=s, j=mid+1; i<=mid || j<=e;)
    {
        if(i<=mid && (arr[i]<=arr[j] || j>e)) t.push_back(arr[i++]);
        else { t.push_back(arr[j++]); ans+=mid-i+1; }
    }

    for(i=0; i<t.size(); i++) arr[s+i]=t[i];
}

int main()
{
    ios_base::sync_with_stdio(false);
    int i;

    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%d", &arr[i]);

    solve(1, n);

    printf("%lld", ans);
    return 0;
}​