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

문제

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

---

문제 요약

수직선 위의 N개의 좌표 X1, X2, ... Xn이 주어질 때, 모두 좌표 압축을 적용하려고 한다.

 

X를 좌표 압축하면, 수직선 위에 X보다 작은 좌표 수가 된다.

(같은 값의 좌표가 여러 개일 경우, 1개로 생각한다.)

 

각 좌표에 압축을 적용한 결과를 출력한다.

---

코드

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

using namespace std;

int n;
int arr[1000010];
vector<int> v;

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        v.push_back(arr[i]);
    }

    set<int> s(v.begin(), v.end());

    vector<int> uv(s.begin(), s.end());

    sort(uv.begin(), uv.end());

    for (int i = 0; i < n; i++) {
        cout << lower_bound(uv.begin(), uv.end(), arr[i]) - uv.begin() << " ";
    }


    return 0;
}

---

코드 설명

1. arr 배열에는 입력 받은 순서대로 원래 좌표들을 저장한다.

+ 동시에 벡터 v에도 좌표들을 담는다.

 

2. v를 집합으로 만들어 중복 값을 모두 제거한 후, 다시 벡터 uv로 변경한다.

 

3. 각 좌표들보다 작은 좌표의 개수를 lower_bound, 즉 이진 탐색을 통해 찾기 위해 정렬한다.

 

4. 각각 lower_bound 함수를 통해 인덱스 번호(개수)를 찾아 출력한다.

---

고찰

벡터 내 원소들의 중복을 제거하는 방법은 해당 원소들로 집합을 만드는 것이다.

set<int> s(v.begin(), v.end());

 

 

그리고 다시 집합을 벡터로 정의한다.

vector<int> uv(s.begin(), s.end());

 

추가로, lower_bound의 반환 값은 주소이기 때문에 첫 주소를 빼주어야 인덱스 번호를 얻을 수 있다.