[백준][이분 탐색] 18770 c++ 구현

목차

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

18870번: 좌표 압축

문제

 

문제 풀이

나는 중복을 제거해준 정렬된 배열을 따로 만들어 이분 탐색을 하는 식으로 코드를 구현했다.

 

 

 

코드 구현

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

vector <pair<int, int>> v;   //벡터 페어로 각각 개수 저장
vector <int> sort_v;    //정렬된 중복x  배열
int main()
{
    int n, i, num, start, end;

    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> num;
        v.push_back(make_pair(num, 0));
        sort_v.push_back(num);
    }
    sort(sort_v.begin(), sort_v.end());  //정렬
    sort_v.erase(unique(sort_v.begin(), sort_v.end()), sort_v.end());  //중복 제거 
  
    for (i = 0; i < n; i++) {  //이분탐색 시작
        start = 0;  //시작점
        end = sort_v.size() - 1;  //끝점
        while (start <= end) {
            int mid = (start + end) / 2;  
            if (sort_v[mid] < v[i].first) {
                start = mid + 1;
            }
            else if (sort_v[mid] > v[i].first) {
                end = mid - 1;
            }
            else {
                v[i].second = mid;
                break;
            }

        }
    }

    for (i = 0; i < n; i++) {
        cout  << v[i].second<<" ";
    }

}