백준 18870 좌표 압축 / C++

문제 : 18870

풀이 point

이진 검색을 활용한 값 / 좌표 압축을 활용하는 문제이다.
$X_{1} \sim X_{N}$ 까지 입력 받은 요소들을 정렬한다. 정렬된 요소들을 통해 이진 검색을 실행한다.

풀이 방법

중복 제거와 이진 검색 모두 C++ 라이브러리의 함수로 대체 가능하다.

std::unique()함수는 연속으로 중복되는 요소만 삭제하기 때문에 반드시 정렬 후 사용하여야한다.

이진 검색 대신 C++ 라이브러리 함수 lower_bound()를 이용할 수 있다.

lower_bound는 찾으려하는 값과 같거나 큰 요소의 맨 첫번째 등장 위치를 반환한다.
반환 타입은 iterator다.

나의 코드는 set을 활용한 중복제거 및 이진검색으로 탐색한 코드이다.

코드

//백준 18870, 좌표 압축

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

int arr[1'000'000];
int copy[1'000'000];
std::vector<int> sorted;
int N;
std::set<int> set;

void bs(int i){
    int st{0}; int end = sorted.size();
    while(st < end){
        int mid = (st+end) / 2;
        if(sorted[mid] >= arr[i]) end = mid;
        else st = mid +1;  
    }
    std::cout << st << ' ';
}

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

    std::cin >> N;
    for(int i{0}; i<N; ++i) std::cin >> arr[i];
    std::copy(arr, arr+N, copy);
    for(int i{0}; i<N; ++i){
        set.insert(copy[i]);
    }

    for(auto n : set){
        sorted.push_back(n);
    }

    std::sort(sorted.begin(), sorted.end());

    for(int i{0}; i<N; ++i){
        bs(i);
    }

    return 0;
}