BOJ 18870 - 좌표 압축 / C++

문제 링크 : https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

 

풀이

입력받은 배열을 정렬한 뒤 0부터 차례대로 우선순위를 매긴다. 중복되는 수들은 건너뛴다.

map 자료구조에 key 값은 수(좌표), value는 우선순위를 넣어준 다음

원래 배열의 순서대로 우선순위를 알맞게 출력한다.

 

코드

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    map<int, int> m;
    vector<int> v;
    vector<int> ans;
    int n;
    
    cin >> n;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    ans = v;
    sort(v.begin(), v.end());

    m.insert(make_pair(v[0], 0));
    int cnt = 1, prior = v[0];
    for(int i=1; i<v.size(); i++){
        if(v[i] == prior) continue;
        else {
            m.insert(make_pair(v[i], cnt++));
            prior = v[i];
        }
    }

    for(int i=0; i<ans.size(); i++){
        cout << m[ans[i]] << ' ';
    }
}