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

블로그에 올리는 모든 문제 풀이는 깃허브에 올려져 있습니다.

---

문제 설명

• 수직선 위에 N개(1 <=N <=1,000,000)의 좌표가 주어진다.
• 둘째 줄에는 공백 한 칸으로 구분된 좌표들이 주어진다. 각 좌표들의 범위는 (-10^9 <=X <=10^9)이다.
• 좌표 압축한 결과를 구하는 프로그램을 작성하시오.

---

풀이 전략

• 출력의 기준이 되는 벡터와 정렬할 벡터 2가지로 구분
• 정렬 후 동일 좌표 제거 후 벡터의 사이즈 변경(동일 값 지우기)
• lower_bound를 이용하여 정렬한 값에서 원본 값을 찾은 후 출력한다.

소스 코드

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

using namespace std;
int main()
{
    vector<int> vec;
    vector<int> org;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        vec.push_back(x);
        org.push_back(x);
    }

    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());

    for (int x : org)
    {
        int print = lower_bound(vec.begin(), vec.end(), x) - vec.begin();
        cout << print << ' ';
    }
}

---

링크

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

18870번: 좌표 압축