18870 번 : 좌표 압축

문제는 다음과 같습니다.

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

18870번: 좌표 압축

 

풀이 과정은 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    
    vector<int> v1, v2;
    int N;
    int input;
    
    cin >> N;
    
    for(int i{0}; i < N; i++) {
        cin >> input;
        v1.push_back(input);
        v2.push_back(input);
    }
    
    
    sort(v1.begin(), v1.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());
    
    for(int i{0}; i < N; i++) {
        cout<<lower_bound(v1.begin(),v1.end(),v2[i])-v1.begin()<<" ";
    }
    
}

문제 해석이 오래 걸렸던 문제입니다.

좌표를 압축한다는 말을 잘 접하지 못할뿐더러, 백준에 제시된 설명이 조금은 불친절하다(설명이 부족하다)고 느껴지기 때문입니다.

아무튼 좌표를 압축한다는 뜻은 " 입력받은 수 중에서 몇 번째로 작은 수인가? "를 뜻한다고 보면 될 것 같습니다.

원래의 뜻은 그 수보다 입력받은 수열 중에서 작은 수가 몇 개나 있는 지를 확인하는 거지만 비슷하다고 생각합니다.

vector를 2개 만들어서 하나는 정렬하여  순서로 사용하였습니다.

이 과정에서 접하게 되는 명령어 중, lower_bound는 이중탐색을 통해 입력받은 값 이상의 값을 가지는 iterator를 반환해 줍니다.

이를 이용해서 좌표를 압축하여 출력할 수 있습니다.