버블 소트 - 1517

//1517 - 버블 솔트
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
pair<int, int> arr[500000];
 
struct FenwickTree
{
    vector<int> tree;
    
    FenwickTree(int n) : tree(n, 0) {}
 
    int sum(int pos)
    {
        ++pos;
        int ret = 0;
        while(pos)
        {
            ret += tree[pos];
            pos &= (pos - 1);
        }
        return ret;
    }
 
    void add(int pos, int val)
    {
        ++pos;
        while(pos < tree.size())
        {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
};
 
void init()
{
    cin >> N;
    for(int i = 0; i<N; ++i)
        cin >> arr[i].first, arr[i].second = i;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    sort(arr, arr+N);
    FenwickTree fwt(N+1);
    long long ans = 0;
    for(int i = N-1; i>=0; --i)
    {
        int t = arr[i].second - fwt.sum(arr[i].second);
        fwt.add(arr[i].second, 1);
        ans += (i - t);
    }
    cout << ans;
}

 

 

 

 

 

 

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

1517번: 버블 소트

 

 

 

 

 

 

버블 소트

버블정렬 알고리즘에 대한 이해가 있어야 되는 문제였습니다.

버블정렬 알고리즘은 맨 마지막부터 맞춰나가는 정렬과 비슷합니다.

즉 전체 배열을 보고 가장 큰것을 맨 마지막으로 이동시키고, 

아직 미완성인 배열에서 가장 큰것을 미완성된 배열의 맨 마지막으로 이동시키고

... 와같은 동작을 반복적으로 수행하여 정렬하는 매커니즘을 가집니다.

즉 swap이 일어나는 횟수는 각각 단계의 미완성된 배열에서 가장 큰 값을 가지는 수의 현재위치를 해당 배열의 가장 마지막 위치로 옮길때 일어나는 swap의 횟수를 구해 모두 더해주면 됩니다.

이때 정해진 시간을 맞추기 위해서 부분문제에서 가장 큰 값을 뒤로 옮겼을때 나머지 수들의 위치를 일일히 조정해 주지 않고, 펜윅트리를 이용해 조정해주어 빠르게 계산이 가능하도록 했습니다.