[백준 18870] 좌표 압축

🔗알고리즘 문제

처음 풀어본 좌표압축 문제이다. 처음 본 유형의 문제이지만 어렵지 않은 개념이라 쉽게 해결할 수 있던 문제이다.

문제 분석

이 문제는 수직선 위에 있는 좌표의 값을 자신보다 작은 좌표의 갯수로 변환하는 문제이다.

예를 들어 1부터 10까지의 수직선 위에 3 5 6 9의 좌표가 있다면 이는 0 1 2 3으로 변환할 수 있다.

발상 & 알고리즘 설계

자신보다 작은 값이 몇개 있는지 찾는 것이 풀이의 핵심이기 때문에 입력받은 좌표를 오름차순으로 정렬한 새로운 벡터를 만들었다.

정렬된 벡터를 앞에서부터 탐색하며 현재까지 찾은 가장 작은 값을 저장해주었다. 다음 탐색하는 값이 현재까지 찾은 가장 작은 값보다 작다면 해당 값이 몇번 째로 작은 값인지 저장해주었다.

코드

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

using namespace std;

int main(){
    int n;
    
    vector<int> v;
    vector<pair<int, int>> s;

    cin >> n;

    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        v.push_back(input);
        s.push_back({ input, i });
    }

    sort(s.begin(), s.end(), [](pair<int, int> a, pair<int, int> b){
        return a.first < b.first;
    });

    int x = 0;
    int last = s[0].first;
    for(int i = 0; i < n; i++){
        if(s[i].first != last){
            ++x;
            last = s[i].first;
        }
        v[s[i].second] = x;
    }

    for(int i = 0; i < n; i++){
        cout << v[i] << " ";
    }
}