백준 18870번: 좌표 압축

문제

문제 바로가기> 백준 18870번: 좌표 압축

풀이

값과 인덱스를 pair로 저장한 후 값을 기준으로 정렬하고 반복문을 돌면서 해당 개수를 count해주는 방식으로 문제를 풀었다.

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin>>n;
    vector<pair<int, int>> v;
    vector<int> ans(n);
    for(int i=0; i<n; i++){
        int tmp; cin>>tmp;
        v.push_back(make_pair(tmp, i));
    }
    sort(v.begin(), v.end());
    int cnt = 0;
    for(int i=0; i<=n-1; i++){
        if(i!=0 && v[i].first == v[i-1].first) cnt--;
        ans[v[i].second] = cnt++;
    }
    for(int i=0; i<n; i++) cout << ans[i] << ' ';
}

다음과 같이도 풀 수 있다.
erase(int start, int end) : 해당하는 범위의 원소를 지움 (start는 포함, end는 포함 x)
unique(v.begin(), v.end()): 중복되지 않는 원소들로 앞에서부터 채움 (정렬 후 적용, 남은 뒷부분은 기존 vector 원소값 존재, 원본이 유지 된 원소들의 첫번째 주소 값 반환)
lower_bound(v.begin(), v.end(), value): 범위에서 value 값이 나타나는 하한을 반환

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    vector<int> v1, v2;
    int n; cin>>n;  
    for(int i=0; i<n; i++){
        int tmp; cin>>tmp;
        v1.push_back(tmp);
        v2.push_back(tmp);
    }
    sort(v1.begin(), v1.end());
    v1.erase(unique(v1.begin(), v1.end()), v1.end());
    for(int i=0; i<n; i++) cout << lower_bound(v1.begin(), v1.end(), v2[i]) - v1.begin() << ' ';
}