백준 18870 좌표압축 c++ // 이분탐색

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

18870번: 좌표 압축

1. 시행착오

답 : 해당원소보다 작은 원소의 갯수

upper_bound - lower_bound 하면 정답이 아니다...

lower-begin 이 정답이다.

 

2. 전체코드

#include <bits/stdc++.h>
using namespace std;

int n,m;
vector<int> v1,v2;
set<int> s;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while (n--) {
        int temp;
        cin >> temp;
        v1.push_back(temp);
        s.insert(temp);
    }
    for (auto i : s) {
        v2.push_back(i); //중복제거한 벡터
    }
    sort(v2.begin(), v2.end());
    
    for (auto i : v1) {
        cout << lower_bound(v2.begin(), v2.end(), i)
            - v2.begin() << " ";
    }
    return 0;
}