문제

수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.

접근방식 1 (구조체)

구조체배열에 value와 index를 저장한 후, value값만 비교해서 정렬을 한다.
그 다음엔 앞의 수와 비교해서 정렬한 index 값을 value에 넣는다.
마지막으로 배열의 index값만 비교해서 처음과 같은 상태로 만든 후, index에 맞게 출력한다.

#include <bits/stdc++.h>
using namespace std;
struct y{
    int i,v;
};
bool cmpv(const y&a,const y&b){
    if(a.v<b.v)return true;
    return false;
}
bool cmpi(const y&a,const y&b){
    if(a.i<b.i)return true;
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    int n,m=0;
    y x;
    vector<y> a;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> x.v;
        x.i=i;
        a.push_back(x);
    }sort(a.begin(),a.end(),cmpv);
    for(int i=0; i<n; i++){
        if(a[i].v==a[i+1].v)a[i].v=m;
        else a[i].v=m++;
    }sort(a.begin(),a.end(),cmpi);
    for(auto i : a)cout << i.v << ' ';
}