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

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

---

좌표 압축 문제는 압축 전 좌표를 기준으로 정렬한 후, 각각의 좌표를 압축하고, 좌표를 입력 받은 순서대로 다시 정렬하면 해결할 수 있습니다.

 

⚠️ 단, 서로 다른 좌표의 개수를 구해야하므로, 단순히 정렬된 좌표의 인덱스만으로 압축된 좌표를 구할 수 없습니다.

좌표 정렬 후, 가장 작은 좌표부터 시작하여, 현재 좌표가 이전 좌표와 같을 경우 좌표를 압축한 결과가 같도록 하고, 이전 좌표보다 클 경우에는 압축한 좌표를 이전 좌표 + 1로 설정해야합니다.

 

아래는 전체 코드입니다. 

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

struct pos {int x1, x2, idx;};   // x1은 기존 좌표, x2는 새로운 좌표, idx는 입력 받은 순서를 나타냄
bool cmp1(pos p1, pos p2){return  p1.x1 < p2.x1;}   // 압축 전 좌표를 기준으로 정렬
bool cmp2(pos p1, pos p2){return  p1.idx < p2.idx;} // 입력 받은 순서를 기준으로 정렬

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<pos> x;
    for(int i = 0; i < n; i++) {    
        int c; cin >> c;
        x.push_back({c, 0, i});
    }

    sort(x.begin(), x.end(), cmp1); // 압축 전 좌표를 기준으로 정렬
    
    x[0].x2 = 0;    // 가장 작은 좌표를 시작점으로 잡음
    for(int i = 1; i < n;){
        if(x[i - 1].x1 == x[i].x1) x[i].x2 = x[i - 1].x2;   // 이전 좌표와 좌표가 같은 경우 압축한 결과가 같도록 함
        else x[i].x2 = x[i - 1].x2 + 1; // 이전 좌표보다 클 경우, 이전 좌표의 압축 결과 + 1
        i++;
    }

    sort(x.begin(), x.end(), cmp2); // 입력 받은 순서를 기준으로 정렬
    for(auto c : x) cout << c.x2 << " ";
}