[백준] 18870 좌표 압축

문제 :

www.acmicpc.net/problem/18870

18870번: 좌표 압축

분석 :

좌표 압축은 수직선 상 넓은 범위에 비해 적은 점을 찍는 것이 비효율적이라는 점에서 고안한 기술이다. ( 위 블로그를 참고하였다.)

점의 좌표를 인덱싱하여 정렬된 순서로 번호를 매기는 방식이다.

 

unique : 

ex > unique(index.begin(), index.end())

index 라는 벡터의 처음부터 끝까지 중복되지 않게 원소를 재배열한다.

만약 벡터 안에 

- 10, 2, 4, 4, 9 가 있다면 -10, 2, 4, 9 로 만든다 !! 뒤에는 무슨 다른 숫자가 붙는 거 같은데 이해가 잘 되지 않는 부분 ..

 

lower_bound : 

ex> lower_bound(index.begin(), index.end(), c)

index 라는 벡터의 처음부터 끝까지 중에 값이 c 이상인 인덱스를 찾는다. 

 

upper_bound :

ex> upper_bound(index.begin(), index.end(), c)

index 라는 벡터의 처음부터 끝까지 중에 값이 c가 초과되는 인덱스를 찾는다. 

 

 

 

 

c++ 코드 :

//
//  18870_cc.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/18.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;



int main(){
    
    int N;
    cin >> N;
    vector<int> index(N);
    vector<int> points(N);
    
    for(int i = 0; i < N; i ++){
        cin >> index.at(i);
        points.at(i) = index.at(i);
    }
    sort(index.begin(), index.end());
    index.erase(unique(index.begin(), index.end()), index.end());
    
    for(auto& c : points){
        cout << lower_bound(index.begin(), index.end(), c) - index.begin() << " ";
    }
    cout << endl;
    
    return 0;
}