[BOJ/백준] 4442번 - 빌보의 생일

문제 링크

• http://icpc.me/4442

문제 출처

• ICPC > Regionals > North America > Pacific Northwest Regional > 2012 Pacific Northwest Region Programming Contest H번

사용 알고리즘

• 세그먼트 트리(Inversion Counting)

시간 복잡도

• O(NlogN)

풀이

서로 다른 순서로 앉은 쌍의 최솟값을 구하기 위해 Inversion Counting을 사용합니다.

입력이 String으로 들어오기 때문에, string과 인덱스를 받을 자료구조가 필요하므로 map을 사용합니다.

• std::map은 검색(find), 삽입(insert), 제거(erase) 작업을 log 시간에 수행할 수 있습니다.

전체 코드

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

#define INF 1e9
#define ll long long

const int mxN=1e5+10;
int n;
vector<ll> arr, tree;
unordered_map<string, int> mp; 

ll sum(int start, int end, int node, int left, int right) {
    if(right < start || end < left) return 0;
    if(left <= start && end <= right) return tree[node];

    int mid = start + (end-start)/2;
    return sum(start, mid, node*2, left, right) + sum(mid+1, end, node*2+1, left, right);
}

void update(int start, int end, int node, int index, int diff) {
    if(index < start || end < index) return;

    tree[node] += diff;
    if(start == end) return;

    int mid = start + (end-start)/2;
    update(start, mid, node*2, index, diff);
    update(mid+1, end, node*2+1, index, diff);
}

void Init() {
    arr.clear();
    tree.clear();
    mp.clear();
}


int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    while(1) {
        cin >> n;
        if(n==0) break;
        arr.resize(n); tree.resize(4*n);

        Init();

        for(int i=0; i<n; i++) {
            string s; cin >> s;
            mp.insert({s, i});
        }

        for(int i=0; i<n; i++) {
            string s; cin >> s;

            auto it = mp.find(s);
            arr[i] = it->second;
        }

        ll ans=0;
        for(int i=0; i<n; i++) {
            int now = arr[i];
            ans += sum(0, n-1, 1, now+1, n-1);
            update(0, n-1, 1, now, 1);
        }

        cout << ans << "\n";
    }
}