[BOJ] #18870 좌표 압축

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

18870번: 좌표 압축

---

백준 단계별 풀어보기 정렬 탭에서 가장 티어가 높았던 문제였다. 높다해도 실버2 정도기에 vector 정렬을 이용한다면 간단히 풀 수 있었다.

하지만 이 문제의 관건은, 주어지는 N의 범위가 최대 1,000,000이므로, 최대한 O(N^2)를 이용하지 않고 풀어내는 것이다. 필자 또한 처음에 기본 반복문 안에 vector를 find하는 함수를 넣어서 풀다가 시간 초과를 내었다. 이는 algorithm의 lower_bound를 이용하면 쉽게 풀 수 있다. lower_bound함수는 O(logN)의 시간복잡도를 가지는 함수이기에, 반복문 안에 넣어도 O(NlogN)이 되게때문에 시간초과를 방지할 수 있다.

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

using namespace std;

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

    int N;
    cin >> N;

    vector<int> firstV, sortV, totalV;
    for (int i=0; i<N; i++) {
        int a;
        cin >> a;
        firstV.push_back(a);
        sortV.push_back(a);
    }
    sort(sortV.begin(), sortV.end());
    sortV.erase(unique(sortV.begin(), sortV.end()), sortV.end());
    //sortV 정렬 후 중복제거    

    for (int i=0; i<N; i++) {
        int target = firstV[i];

        int idx = lower_bound(sortV.begin(), sortV.end(), target) - sortV.begin();
        //find(sortV.begin(), sortV.end(), target) - sortV.begin();
        totalV.push_back(idx);
    }
    //sortV에서 target 탐색 후, 해당 idx totalV에 삽입

    for (int it : totalV) cout << it << " ";
    printf("\n");

    return 0;
}

---

vector 정렬 시, 중복된 값 제거하고 정렬

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

sortV.erase(unique(sortV.begin(), sortV.end()), sortV.end());

unique로 중복된 원소들을 배열의 맨 끝부분으로 보낸 후, 중복된 원소들의 집합중 맨 처음 포인터 위치를 return
unique로 return된 위치부터 배열의 끝부분까지의 원소들을 erase로 삭제

결과적으로 중복된 원소들을 모두 제거하고 정렬된 배열만 남게 됨

lower_bound & upper_bound | 이진탐색으로 원소를 탐색하는 함수

int idx = lower_bound(sortV.begin(), sortV.end(), target) - sortV.begin();

totalV.push_back(idx);

lower_bound : 찾으려는 값보다 크거나 같은 숫자가 배열 몇 번재에서 처음 등장하는지 찾음
upper_bound : 찾으려는 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾음
둘 모두 탐색을 진행할 배열이 오름차순 정렬되어 있어야 함

이 함수의 반환형은 Iterator 이므로 실제로 몇 번째 인덱스인지 알고 싶다면,
위 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 빼주면 됨.