[18870] 좌표 압축

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

18870번: 좌표 압축

<문제>

좌표압축은 naive로 풀기 어려울때, 다른 알고리즘을 적용하기 좋게 전처리하는 느낌인듯 싶다.

값의 범위가 상당히 줄어듦에 이점이 있어 counting sort처럼 값의 개수등을 저장하는 선형 자료구조를

MLE에 대한 걱정없이 선언할 수 있으나 압축후에는 값간의 대소관계만이 남음에 유의해야한다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
vector<pi> v;
vector<int> ans;
int n;
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    v.resize(n);
    ans.resize(n);
    int i;
    for (i = 0; i < n; i++) {
        int x;
        cin >> x;
        v[i] = {x, i};
    }
    sort(v.begin(), v.end());
    int val = 0;
    for (i = 0; i < n; i++) {
        if (i != 0 && v[i - 1].first != v[i].first) val++;
        ans[v[i].second] = val;
    }
    for (i = 0; i < n; i++) cout << ans[i] << ' ';
    return 0;
}