[c++][문제 풀이] 백준 18870번 <좌표 압축>

문제 설명

 

입력된 값들 각각 자신 보다 작은 값이 몇 개 있는 지를 입력된 순서대로 출력 하면 되는 문제이다.

단 , 자신 보다 작은 값을 셀 때 중복 된 값들은 1개로 처리 된다.

 

문제 풀이

 

시간 제한은 2초.

입력 값은 0 ~ 10^6 까지 이다.

 

시간복잡도 O(N^2) 로는 풀 수 없고 O(NlogN) 으로 풀어야 한다.

 

algorithm 의 sort 함수 -> O(NlogN)

algorithm 의 lower_bound ->(O(logN) 함수 * N번) 를 사용할 것이다.

 

Coding

 

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

using namespace std;

int main(int args ,char ** argv){
    
    int N; // 좌표의 갯수
    int X; // 좌표 값

    vector<int> v; // 중복 제거 , 오름차순 정렬 할 벡터

    cin >> N;

    while(N--){
        cin >> X;
        v.push_back(X);     
    }

    vector<int> v_before(v); // 입력 된 그대로의 벡터.

    sort(v.begin() , v.end()); // 오름차순 정렬
    v.erase(unique(v.begin() , v.end()), v.end()); // 중복 제거

    vector<int> result;

    for(int i = 0 ; i < v_before.size() ; ++i){
            result.push_back(lower_bound(v.begin() , v.end() , v_before[i]) - v.begin()); 
    }

    for(auto x : result){
        cout << x << ' ';
    }

}

 

unique , lowerbound 함수에 대해 잘 모르겠다면 아래 글들을 참조 하자

2022.02.13 - [c++/문법] - [C++] Unique 함수 정리 및 예제

[C++] Unique 함수 정리 및 예제

2022.02.13 - [c++/문법] - [c++] 이진 탐색 ( lower_bound , upper_bound ) 사용 및 예제

[c++] 이진 탐색 ( lower_bound , upper_bound ) 사용 및 예제

 

 

백준 18870번 문제 링크

 

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

18870번: 좌표 압축