(C++) - 백준(BOJ) 18870번 : 좌표 압축 답

www.acmicpc.net/problem/18870

18870번: 좌표 압축

구현을 해보는 문제였습니다. 문제의 조건이 수식으로 되어있어서 좀 헷갈렸던 것 같습니다. ㅋㅋㅋ

좌표를 압축한다 : 해당 좌표의 값을 그 값보다 작은 좌표값들의 개수로 대체한다의 의미입니다.

 

풀이방법 

 1. 매 좌표마다 값,index를 vector pair형태로 저장한다.

 2. 값을 기준으로(vector.first) 오름차순 정렬

 3. 오름차순 정렬된 상태에서 답을 ans vector에 index 오름차순로 중복을 고려하여 저장

 4. ans vector의 값을 출력

 

Code 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector <pair<int,int>> v;
vector <int> ans(1000001);
int main(){
    cin >> n;
    for(int i =0; i<n; i++){
        int x;
        cin >> x;
        v.push_back({x,i});
    }
    sort(v.begin(),v.end());
    
    int pivot = v[0].first;
    int cnt = 0;
    ans[v[0].second] = 0;

    for(int i = 1; i < n ; i++){
        if(pivot==v[i].first){
            ans[v[i].second] = cnt;
        }else {
            ans[v[i].second] = ++cnt;
            pivot = v[i].first;
        }
    }
    for(int i = 0; i < n ; i++){
        cout << ans[i] << ' ';
    }
}