[Silver II] 좌표 압축 - 18870

문제 링크

문제 링크

성능 요약

메모리: 18232 KB, 시간: 912 ms

문제 설명

수직선 위에 N개의 좌표 X₁, X₂, ..., X_N이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

X_i를 좌표 압축한 결과 X'_i의 값은 X_i > X_j를 만족하는 서로 다른 좌표 X_j의 개수와 같아야 한다.

X₁, X₂, ..., X_N에 좌표 압축을 적용한 결과 X'₁, X'₂, ..., X'_N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X₁, X₂, ..., X_N이 주어진다.

출력

첫째 줄에 X'₁, X'₂, ..., X'_N을 공백 한 칸으로 구분해서 출력한다.

코드

#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] << ' ';
    }
}