백준 18870번 좌표 압축 (C++)

문제 링크 : www.acmicpc.net/problem/18870

18870번: 좌표 압축

문제를 한 줄 요약하자면, 배열에 입력된 각 값들의 크기 순서를 출력해주면 된다.

작은 값일수록 작은 순서를 지니게 되며, 이때 순서는 0부터 시작된다.

한 가지 중요한 점은, 중복된 값의 원소들은 중복된 순서를 가지게 된다는 것이다.

 

문제 풀이는 다음과 같다. 

1. 배열에 값을 입력받고, 이를 복사한 배열을 하나 더 만든다. 이때 배열, 벡터 어느쪽을 사용해도 무관하다.

2. 복사한 배열에서 중복된 값을 없앤다. (erase와 unique 조합을 활용)

3. 원본 배열의 사이즈만큼 for문을 돌린다. 이때 원본배열의 값의 순서를 중복값을 제거한 2번 배열에서 찾아주면 된다.

 

입력할 수 있는 최대 범위는 1,000,000이기 때문에, 무턱대고 2중 for문으로 값을 비교하면서 풀었다가는 시간초과가 날 수 밖에 없다.

이 문제를 풀기 위해 처음으로 lower_bound를 활용해보았는데, 번거롭게 이분탐색을 구현하지 않아도 돼서 편리했다. 

lower_bound와 자매품 upper_bound의 설명은 해당 링크를 통해 확인해보자.

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

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, temp = 0;
    cin >> n;
    vector<int> v;
    vector<int> vc;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        v.push_back(temp);
        vc.push_back(temp);
    }
    sort(vc.begin(), vc.end());
    vc.erase(unique(vc.begin(), vc.end()), vc.end()); // 중복제거
    for (int i = 0; i < v.size(); i++) {
        cout << lower_bound(vc.begin(), vc.end(), v[i]) - vc.begin() << " ";
    }
    cout << "\n";
    return 0;
}

무턱대고 돌려버린 2중 for문의 흔적