[ 백준 / C++ ] 1517 : 버블 소트

[ 문제 ]

 

1517번: 버블 소트 (acmicpc.net)

 

[ 접근방법 ]

 

버블 정렬을 할 때 교환 횟수는 i <= j, a[ i ] > a[ j ] 인 쌍의 개수와 같다. ( 코딩 편의를 위해 i < j 대신 i <= j 고려 )

j를 1부터 n까지 살펴보면서 위 조건을 만족하는 i의 개수를 더해주면 된다.

 

a[ i ] > a[ j ]를 빠르게 판단하기 위해 정렬을 진행했다.

정렬 후의 index와 정렬 전의 index를 자유롭게 매칭하기 위해 value와 index를 넣은 pair 배열을 만들고 정렬했다.

 

aIndex[ j ]는 정렬 전 index j의 정렬 후 index를 의미한다.

정렬 전 a[ j ] = 정렬 후 a[ aIndex[ j ] ].

 

j를 1부터 n까지 살펴보면서 위 조건을 만족하는 i의 개수를 빠르게 판단하기 위해 BIT를 만들었다.

sum과 add 함수는 BIT를 위한 함수들이다.

 

add( aIndex[ j ], 1 )를 통해 a[ j ]에 해당하는 값을 BIT에 체크해준다.

sum( aIndex[ j ] )은 i <= j, a[ i ] <= a[ j ] 인 쌍의 개수를 리턴한다.

따라서 j - sum( aIndex[ j ] )은 i <= j, a[ i ] > a[ j ] 인 쌍의 개수를 나타내고 이를 ans에 더해주며 for문을 돌아준다.

 

[ 소스코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

pair<int, int> a[500005];
ll n, ans, bit[500005], aIndex[500005];

long long sum(int i){
    long long res = 0;
    while(i > 0){
        res += bit[i];
        i -= i & -i;
    }
    return res;
}

void add(int i, int x){
    while(i <= n){
        bit[i] += x;
        i += i & -i;
    }
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        aIndex[a[i].second] = i;
    }

    for(int j = 1; j <= n; j++){
        add(aIndex[j], 1);
        ans += j - sum(aIndex[j]);
    }

    cout << ans;

    return 0;
}