[백준/C++] 18870번 좌표 압축

문제: www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

 

문제풀이

 

입력되는 좌표 Xn에 대하여 Xn 보다 작은 좌표의 수를 각각 출력해주는 문제이다.

 

좌표의 개수는 1000,000으로 1000,001 크기의 벡터를 선언하여 벡터의 인덱스를 이용해 문제를 풀었다.

 

pair 벡터를 선언해 {좌표, 순서} 순으로 저장하고 좌표를 기준으로 오름차순 정렬했다.

이후 벡터를 탐색해 좌표 크기 순서대로 정답 벡터에 압축한 좌표의 수를 저장하고

정답 벡터를 출력했다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N;
    cin>>N;

    vector<pair<int ,int>> v;
    vector<int> rv(1000001);
    for(int i=0; i<N; i++){
        int x;
        cin>>x;
        v.push_back({x, i});
    }

    sort(v.begin(), v.end());

    int pre = v[0].first;
    int cnt = 0;
    for(int i=0; i<N; i++){
        if(pre != v[i].first){
            rv[v[i].second] = ++cnt;
            pre = v[i].first;
        }
        else{
            rv[v[i].second] = cnt;
        }
    }

    for(int i=0; i<N; i++){
        cout<<rv[i]<<" ";

    }

    return 0;
}

 

 

결과