문제

---

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

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

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

입력

---

첫째 줄에 N이 주어진다.

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

• 제한
  1 ≤ N ≤ 1,000,000
  -109 ≤ Xi ≤ 109

출력

---

풀이

---

주어진 좌표에 대해 오름차순으로 나열하여 낮은 좌표부터 0번을 부여하고
그 다음 순서의 좌표에는 다음 인덱스 값을 부여하여 압축하는 방식이다.

따라서 입력으로 받은 좌표들을 2개의 벡터에 저장하고
한 개의 벡터는 중복을 제거하여 오름차순으로 정렬한다.

이후 정렬한 벡터에 대해 기존의 좌표를 가진 벡터의 요소를 하나하나 찾아서
정렬했을 때 몇 번째에 위치하는 지 구한다.

코드

---

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


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;

    cin >> N;
    vector<long long> my_v;
    vector<long long> temp;

    for (int i = 0; i < N; i++)
    {
        long long a;
        cin >> a;
        temp.push_back(a);

        my_v.push_back(a);
    }

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

    for (int i = 0; i < N; i++)
    {
        cout << lower_bound(my_v.begin(), my_v.end(), temp[i]) - my_v.begin() << " ";
    }

    return 0;
}

리뷰

사실 구현하기 위한 아이디어는 바로 떠올라서 바로 코드를 작성하고자 했으나

벡터 내의 요소에서 중복을 제거한 채 정렬하기,
벡터 요소의 순서를 알기 위해 2중 for 문을 통해 찾게 될 경우 시간 초과가 발생하고,
find 를 통해 찾을 경우에도 시간 초과가 발생한다.

위의 문제에 막혀 구현에 어려움을 겪었고 이진 탐색과 unique 의 사용에 대해 찾아본 후에야
구현할 수 있었다.

탐색에 있어 시간 초과가 발생할 경우
이진 탐색(binary_search, lower_bound, upper_bound)을 고려하는 방법과

벡터의 요소를 다루는 과정 (unique) 에 대해 배울 수 있어서 이를 정리하는 것이 필요할 듯 하다!