좌표 압축

개념

수의 범위의 비해 값과 무관하게 수의 대소 관계만을 알면 될 때 수에 새로운 인덱스를 부여하여 수의 범위를 줄이는 기법

구현 과정

1. 입력 배열의 값의 중복을 제거하여 오름차순으로 정렬한다.
2. 압출 자료구조를 활용하여 새로운 인덱스로 변환된 결과 배열을 생성한다. (lower_bound 사용)

boj 18870(좌표 압축) 소스 코드

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

vector<int> num, v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n; num.reserve(n);
    for(int i=0; i<n; i++) {
        cin >> num[i]; v.push_back(num[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i=0; i<n; i++) cout << lower_bound(v.begin(), v.end(), num[i])-v.begin() << ' ';
}