[백준] 18870.cpp : 좌표 압축

www.acmicpc.net/problem/18870

18870번: 좌표 압축

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> data(n);            // 실제 데이터들 그대로 담을 배열
    vector<int> answer(n);          // 좌표 압축할 배열
    for(int i = 0 ; i < n ; i++)
    {
        cin >> data[i];
        answer[i] = data[i];
    }
    sort(answer.begin(), answer.end());                                     // 우선 오름차순 정렬을 해준 뒤
    answer.erase(unique(answer.begin(), answer.end()), answer.end());       // 중복되는 값들을 제거해주면 인덱싱 성공
    for(int i = 0 ; i < n ; i++)
    {
        cout << int(lower_bound(answer.begin(), answer.end(), data[i]) - answer.begin()) << " ";    // 인덱싱된 값 출력
    }
    cout << '\n';
}

 

[Approach]

1. N 이 백만이니까 시간복잡도를 잘 따져야 될 것 같다. DP 배열 사용이 가능할까?

     -> 좌표 압축 기법에 대해서 찾아보았음

 

[Point]

1. 범위가 클 때 해당 범위를 필요한 만큼만으로 줄여서 사용하기. 순서가 중요할 때

2. unique 동작 원리 + erase 랑 같이 사용해서 중복 제거하기

3. 전에도 배웠던 lower_bound 를 통해 벡터에서 값 찾기