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

문제 이해

- N개의 좌표: X1, ..., Xn 이 있다.

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

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 512MB

 

<입력>

N: 좌표의 개수 (1 ~ 1,000,000, 10^6)

Xi: 좌표 (-10^9 ~ 10^9)

 

<출력>

X1', ..., Xn'을 공백으로 구분하여 출력하라.

 

 

문제 풀이

배열을 두 개 사용하여

하나는 원본 배열,

하나는 중복된 값을 제거한 정렬된 배열 형태로 둔 뒤에,

비교하여 순서를 출력하면 될 것 같았다.

 

 

중복된 값을 제거하고 정렬하는 건 vector에 내장된 unique 함수를 이용하였는데 다음과 같다.

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

 

그런데 결국 두 배열을 비교하는 과정에서 완전 탐색을 하면 O(N^2)의 시간복잡도를 가진다는 결론이 나와 머리가 멍해졌다.

 

 

결론적으로는 탐색 방법으로 이분 탐색을 사용해 시간 복잡도를 O(NlogN)으로 줄여 푸는 문제였다.

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

 

 

전체 코드

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

int num[1010101];
vector<int> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

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

    return 0;
}