BOJ 1517 버블 소트

버블 소트

(http://boj.kr/1517)

버블 소트의 Swap 횟수는 최악의 경우 n(n+1)/2이기 때문에 직접 버블 소트를 해가며 횟수를 세면 시간 초과이다.

그렇기 때문에 다른 방법으로 알아내야 하는데,

기본적인 아이디어는, 버블 소트는 어떤 수가 자기 자리를 찾기 위해서는, 자신의 왼쪽에 있는 수들 중에서 큰 수들과 바뀌어야 한다는 점이다.

그렇다면 이제 그걸 어떻게 구할지가 문제가 된다.

이 방법은 여러가지가 있는데, 몇 가지를 고르면,

첫 번째 방법으로는 머지 소트 과정에서 그 수를 구하는 것이 있다.

머지 소트 과정에서 왼쪽 배열과 오른쪽 배열을 비교할 때, 만약 왼쪽 배열의 수가 오른쪽 배열의 수보다 크다면 Swap이 일어난다는 것이다.

즉, 왼쪽 배열의 수 > 오른쪽 배열의 수인 경우에 오른쪽 배열의 수의 개수만큼 Swap이 일어난다.

두 번째 방법으로는 구간합을 이용하는 것이다.

물론 구간합을 선형으로 구하면 비효율적이기 때문에 O(logN)으로 구할 수 있는 세그먼트 트리, 바이너리 인덱스 트리 등을 써야한다.

어쨌든 Swap 횟수를 구하는데 구간합을 구하는 방법을 적용하는 법은,

수를 입력받으며 그 수가 몇번 나왔는지 카운트해가며 자기보다 작은 수의 개수를 구할 수도 있겠지만, 이 문제에서 수의 크기 제한은 크기 때문에 적합하지 않다.

그렇기 때문에 우선 수들의 원래 인덱스를 저장해놓고 값을 기준으로 내림차순으로 정렬한다.

그리고 수들을 하나하나 추가해가다 보면, 이미 등록돼있는 수는 자기보다 크다는 것이다.

자기보다 크면서 인덱스가 작다면 Swap이 일어나기 때문에,

수를 추가하면서 자기보다 인덱스가 작은 수의 개수를 구간합으로 구하면 된다.

아래 코드는 바이너리 인덱스 트리로 구현했다.

#include <bits/stdc++.h>
 
using namespace std;
 
struct ar {
    int val, idx;
}arr[500000];
 
bool cmp(ar a, ar b) {
    return a.val > b.val;
}
 
int n, tree[500001];
 
void update(int idx) {
    while (idx <= n) {
        tree[idx]++;
        idx += (idx & -idx);
    }
}
 
int sum(int idx) {
    int ans = 0;
 
    while (idx > 0) {
        ans += tree[idx];
        idx -= (idx & -idx);
    }
 
    return ans;
}
 
int main() {
    int i;
    long long ans = 0;
 
    scanf("%d", &n);
 
    for (i = 0;i < n;++i) {
        scanf("%d", &arr[i].val);
        arr[i].idx = i + 1;
    }
 
    sort(arr, arr + n, cmp);
 
    for (i = 0;i < n;++i) {
        ans += sum(arr[i].idx - 1);
        update(arr[i].idx);
    }
 
    printf("%lld", ans);
 
    return 0;
}