[C++]백준 - 18870번 문제

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

18870번: 좌표 압축

 

18870번 : 좌표 압축

---

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

입력

---

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

 

출력

---

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

 

---

 

생각해 볼 점

---

아무리 용을 써도 시간 초과가 나거나, 어떻게 풀지 감이 잡히지 않아 찾아보니

아예 "좌표 압축 기법"이라는 방법이 존재합니다. 기법으로서 존재할만큼 자주 쓰이니 외워두는 편이 좋겠습니다.

 

참고하기에 좋은 블로그 링크를 남깁니다.

 

 

좌표압축 기법 (tistory.com)

좌표압축 기법

 

코드

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int N;
    vector<int> v;
    cin >> N;
    int *input = new int[N];
    for(int i = 0; i < N; i++)
    {
        cin >> input[i];
        v.push_back(input[i]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
     
    for(int i = 0; i < N; i++)
    {
        int res = lower_bound(v.begin(), v.end(), input[i]) - v.begin();
        cout << res << " ";
    }
    delete[] input;
    return 0;
}

 

그 외

---

lower_bound의 경우, 알고리즘 STL을 사용했으나, 직접 구현하실 경우에는 이진 탐색으로 구현하는 것이 좋습니다.

어차피 정렬된 벡터에서 찾는 것이므로, 이진 탐색을 이용하지 않고 for문을 돌렸다가는 시간 초과가 나기 일쑤입니다.

 

P.S : Set의 iterator는 lower_bound 시, 원하는 값을 얻을 수 없습니다. 트리 형태로 구현되어 있으므로, 순차 배열 방식이 아니기 때문에 그런 것 같습니다.