[백준 18870번 C++] 좌표 압축

18870번: 좌표 압축 (acmicpc.net)

18870번: 좌표 압축

---

문제 이해가 너무 어려웠던 문제

문제 설명이 너무 불친절해요

그래서 구글링해서 해설을 좀 읽어보니까 이해한게

좌표 압축이라는 것은

좌표를 중복되지 않는 집합에 넣어뒀을 때, 자신보다 작은 원소의 개수로 자신의 수를 바꾸는 것 

 

그럼 그렇게 하기 위해서는

배열을 받고, 

오름차순으로 정렬을 해준 뒤,

중복되는 원소를 제거해주고,

자신보다 왼쪽에 있는 원소의 개수를 세어서 바꿔주면 된다

 

---

Unique, Erase 함수

 

중복된 값을 제거하기 위해서

<algorithm> 헤더파일을 사용해서 sort와 erase를 함께 씀

반드시 정렬을 해주고 사용해야하기 때문에 둘이 같이 사용!!

#include <algorithm>

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

 

[C++] Unique 함수 정리 및 예제 (tistory.com)

[C++] Unique 함수 정리 및 예제

.. 그리고 algorithm의 이진 탐색 함수를 사용해서 찾아줬는데 

밑 포스팅을 참고함

 

lower_bound 이진탐색 함수

 

#include <algorithm>

int arr[6] = { 1,2,3,4,5,6 };
cout << lower_bound(arr, arr + 6, 6) - arr << "\n";

 

알고리즘 - c++ lower_bound, upper_bound 활용하기 | ChanBLOG (chanhuiseok.github.io)

알고리즘 - c++ lower_bound, upper_bound 활용하기

좌표 압축 백준 18870번 c++ :: JArchive 프로그래밍 일기 (tistory.com)

좌표 압축 백준 18870번 c++

 

---

 

제 코드는요

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

using namespace std;

int main()
{
    int n, m;
    cin >> n;

    vector<int> v, r;
    for(int i=0; i<n; i++){
        cin >> m;
        v.push_back(m);
        r.push_back(m);
    }
    
    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(), r[i]) - v.begin() << " ";
    }
    
    return 0;
}