[백준 18870] 좌표 압축

문제

www.acmicpc.net/problem/18870

 

알고리즘

좌표압축

 

풀이

상대적인 크기 관계는 유지한 채, 숫자의 크기만 줄이는 테크닉입니다. 이를 위해선 두 개의 배열이 필요합니다. 하나는 원래의 원소를 담고 있는 배열, 나머지는 중복제거를 한 후의 배열입니다. 중복제거를 한 배열의 인덱스가 좌표압축의 결과가 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N;
int arr[1000000];
vector<int> vt;
int main() {
    FAST;
    cin >> N;
    rep(i, N) {
        cin >> arr[i];
        vt.emplace_back(arr[i]);
    }
    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());

    rep(i, N) {
        cout << lower_bound(vt.begin(), vt.end(), arr[i]) - vt.begin() << ' ';
    }

    return 0;
}