백준 18870번, 좌표 압축

백준 18870번 c++ 문제풀이

문제:

백준 18870

풀이:

1. 먼저 두개의 벡터(v1, v)에 좌표 정보를 저장 한다.
2. v벡터는 오름차순으로 정렬 후 중복된 숫자를 지운다.
3. v1에 저장된 좌표의 순서대로 v에 몇번 째로 저장 되어 있는지 찾아 출력한다.
4. 위 과정을 이분 탐색으로 진행하여 시간 초과가 나지 않도록 한다.

코드:

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

using namespace std;

void findplace(vector<int> v, vector<int> v1){
    int mid;
    for(int i=0;i<v1.size();i++){
        int left = 0;
        int right = v.size()-1;
        while(left <= right){
            mid = (left + right)/2;
            if(v[mid] == v1[i]){
                cout << mid << " ";
                break;
            }
            else if(v[mid] < v1[i]){
                left = mid+1;
            }
            else if(v[mid] > v1[i]){
                right= mid - 1;
            }
        }
    }   
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    vector<int> v;
    vector<int> v1;

    cin >> n;
    
    for(int i=0;i<n;i++){
        int input;

        cin >> input;

        v.push_back(input);
        v1.push_back(input);
    }

    sort(v.begin(), v.end());//오름차순 정렬

    v.erase(unique(v.begin(), v.end()), v.end());//중복 지우기.

    findplace(v, v1);

    return 0;
} 

감사합니다.