[BOJ / C++] 좌표 압축 (이분탐색)

문제링크: https://www.acmicpc.net/problem/18870

 

> 방법 1. uniq 배열 직접 구현

1-1. 코드

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

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

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    vector<int> tmp(arr);
    sort(tmp.begin(), tmp.end());

    vector<int> uniq;
    for (int i = 0; i < n; i++) {
        if (i == 0 || tmp[i-1] != tmp[i]) uniq.push_back(tmp[i]);
    }

    for (int i = 0; i < n; i++) {
        cout << lower_bound(uniq.begin(), uniq.end(), arr[i]) - uniq.begin() << ' ';
    }
}

 

 

1-2. 분석

좌표 압축에 해당하는 uniq 배열을 따로 만들어서 구현해준다. 원소가 unique 배열의 몇번째 원소인지는 lower_bound - uniq.begin()으로 계산할 수 있다. lower_bound가 iterator를 반환하기 때문이다.

 

1-3. 시간복잡도

sort에 O(nlgn)이 걸리고, uniq 배열을 만드는데는 O(n)의 시간복잡도가 걸린다. lower_bound의 시간복잡도는 O(lgn)이다.

 

 

> 방법 2. STL (unique) 이용

2-1. 코드

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

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

    int n;
    cin >> n;

    vector<int> arr(n);
    vector<int> uni;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        uni.push_back(arr[i]);
    }
    sort(uni.begin(), uni.end());
    uni.erase(unique(uni.begin(), uni.end()), uni.end());
    
    for (int i = 0; i < n; i++) {
        cout << lower_bound(uni.begin(), uni.end(), arr[i]) - uni.begin() << ' ';
    }
}

 

 

2-2. 분석

STL의 unique는 사용하기전 반드시 미리 정렬이 되어있어야 한다. unique(uni.begin(), uni.end())를 하면 압축을 하고 난 다음 쓰레기 값들이 들어있는 뒤 iterator를 반환한다. 그래서 이 후 부분을 잘라내는 erase랑 함께 쓰이게 된다. 따라서 아래와 같이 쓸 수 있다.

 

uni.erase(unique(uni.begin(), uni.end()), uni.end();

 

 

2-3. 시간복잡도

sort에 O(nlgn)이 걸리고, unique STL에 O(n)의 시간복잡도가 걸린다. lower_bound의 시간복잡도는 O(lgn)이다.