BOJ - 좌표압축(18870)

실버2 : 파라메트릭 서치 문제이다.

Root 찾기

처음에 또다시 해시로 풀려고 하다가, 중간에 입력값의 범위가 후덜덜한 것을 보고 풀이 방법을 바꾸었다. 이 문제를 그냥 linear하게 풀려고 하면 100000번을 linear하게 탐색해야 하기 때문에 터져버린다.

그래서! 이 문제는 파라메트릭 서치로 풀이한다. 하나의 질문에 대해 몇번이 필요한지 사실 결정되어 있다. 입력되는 것들을 집합화 하고, 이것들을 정렬하면, index가 곧 해당 입력의 압축된 좌표이다.

• 입력

5
2 4 -10 4 -9

|집합화|2|4|-10|-9| |:-:------|:|:|:-:|::| |정렬|-10|-9|2|4| |index|0|1|2|3|

잘 보면, 집합화 한 원소를 정렬한 뒤, 이것들을 배열에 넣었을 때, index가 곧 해당 원소의 압축된 좌표이다.

따라서, 이제는 입력된 순서대로 이 index를 찾아주기만 하면 된다. 이 때, 찾는 방법으로 이진 탐색을 사용하면 된다.

Code

#include <iostream>
#include <set>
using namespace std;
int N;
set<int> s;
int arr[1000001];
int net[1000001];
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        s.insert(arr[i]);
    }
 
    int idx = -1;
    for (auto iter = s.begin(); iter != s.end(); iter++) {
        idx++;
        net[idx] = *iter;
    }
 
    for (int i = 0; i < N; i++) {
        int start = 0, end = idx;
        int now = arr[i];
        while (start <= end) {
            int mid = (start+end)/2;
            if (net[mid] > now) {
                end = mid-1;
            } else if (net[mid] < now){
                start = mid+1;
            } else {
                cout << mid << " ";
                break;
            }
        }
    }
    return 0;
}

Reference

• 백준(18870번) - 좌표 압축