[BOJ 1517] 버블 소트

[BOJ 1517] 버블 소트 - P5

문제 설명 :

n개의 수를 버블 소트할 때, swap이 총 몇 번 일어나는지 세야 한다.

문제 풀이 :

i번 째 수를 기준으로 자신의 왼쪽 ( [1, i-1] ) 에 있는 수들 중에서 자신보다 큰 값이 몇 개인지 세면 된다. n이 50만이기 때문에 log 시간만에 세야 한다. 두 가지 풀이가 가능하다.
첫 번째 풀이는 mergesort tree를 이용하면 된다. mergesort tree는 [l,r]구간 상에서 x보다 작은 수의 값을 log만에 구할 수 있다. 이는 얼마 전의 k번째 수 문제에서도 언급했었다.
두 번째 풀이는 바로 offline query를 이용하는 것이다. 이 문제는 쿼리별로 독립시행이다. 즉 이번 쿼리의 정답이 그 이후의 쿼리의 정답에 영향을 끼치지 않는다. 그렇기 때문에 원소 값들을 전처리하여 문제를 풀기에 유리하게끔 만든 뒤에 query를 받을 수 있다는 뜻이다.
이 문제에서 할 전처리는 원소들을 모두 받아서 좌표압축을 진행할 것이다. 좌표압축을 하고 나면 i번째 원소가 전체 원소 중에서 몇 번째 원소인지(오름차순 기준) map에다가 저장을 해 놓을 것이다.
그리고 나서 1번째 인덱스부터 차례로 자신의 왼쪽에 있는 수 중에서 자신보다 큰 값의 개수를 카운트할 것이다. 위에서 좌표압축의 결과를 map에다가 저장해놓았으므로 query는 getSum(1,map[arr[i]]) 같은 형태로 받아서 ans에다가 값을 더해나가면 된다. 그런 다음 update를 통해서 해당 인덱스 값을 1 증가시켜주면 된다.

배울 점 :

offline query와 좌표압축을 통해 i번째 값이 어느 위치(pos)에 들어가게 될 것인지 미리 배정할 수 있고, 이를 query(1,pos)같은 형태로 만들 수 있다.

소스코드 :

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;

const int SIZE = 500009;
int tree[SIZE*8],arr[SIZE];
vector<int> v;
int startIdx=1;

int count(int node,int cl, int cr,int ql,int qr){
    if(cl > qr || ql > cr) return 0;
    if(qr >= cr && cl >= ql) {
        return tree[node];
    }

    int mid = (cl+cr)/2;
    return count(node*2,cl,mid,ql,qr) + count(node*2+1,mid+1,cr,ql,qr);
}

void update(int node){
    node = node + startIdx - 1;
    tree[node]++;
    int par = node / 2;
    while(par >= 1){
        tree[par] = tree[par*2] + tree[par*2+1];
        par /= 2;
    }
    return;
}

int main(){
    int n;    scanf("%d",&n);

    for(; startIdx < n ; startIdx *= 2);
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
        v.push_back(arr[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(),v.end()), v.end());

    map<int,int> compress;
    for(int i=0 ; i<v.size() ; i++){
        compress[v[i]] = i + 1;
    }

    ll ans = 0;
    for(int i=1 ; i<=n ; i++){
        ans += 1LL* count(1,1,startIdx,compress[arr[i]] + 1,startIdx);
        update(compress[arr[i]]);
    }
    printf("%lld\n",ans);
    return 0;
}