[Baekjoon/C++] 좌표 압축 18870번

Baekjoon Online Judge

문제로 이동

 

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

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

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

 

---

예제 입력	예제 출력
5 2 4 -10 4 -9	2 3 0 3 1
6 1000 999 1000 999 1000 999	1 0 1 0 1 0

---

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct coordinate {
    int idx1; // 입력할 때 인덱스
    int idx2; // 정렬한 뒤 인덱스
    int x;
};

// 오름차순
bool compare1(coordinate &a, coordinate &b) {
    return a.x < b.x;
}

// 정렬을 원래대로 돌리기
bool compare2(coordinate& a, coordinate& b) {
    return a.idx1 < b.idx1;
}

int main() {
    int N;
    cin >> N;

    vector<coordinate> x(N);

    // 입력
    for (int i = 0; i < N; i++) {
        cin >> x[i].x;
        x[i].idx1 = i;
    }  

    // 정렬
    sort(x.begin(), x.end(), compare1);

    // 작은 수의 개수 찾기
    int count = 0;
    x[0].idx2 = 0;
    for (int i = 1; i < N; i++) {
        // 같은 숫자가 있을 때
        if(x[i].x == x[i - 1].x)
            x[i].idx2 = count;
        else {
            count++;
            x[i].idx2 = count;
        }
    }

    // 정렬을 원래대로 돌리기
    sort(x.begin(), x.end(), compare2);

    // 출력
    for (int i = 0; i < N; i++)
        cout << x[i].idx2 << " ";

    return 0;
}

입력한 수를 오름차순으로 정렬한 뒤 각 숫자의 인덱스를 이용해서 각 숫자보다 작은 수의 개수를 찾는다. 그 뒤 숫자를 입력할 때 같이 저장된 idx1를 이용해 오름차순으로 정렬된 배열을 원래대로 되돌렸다.