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

www.acmicpc.net/problem/18870

18870번: 좌표 압축

풀이

입력된 수열을 오름차순으로 정렬한 후, 압축합니다.

 

압축할 땐, 넘버링에 쓰일 변수를 유지하며 다음의 원소가 현재 원소보다 크다면

 

넘버링을 하고 1을 증가 시켜 주고, 아니라면 그대로 유지합니다.

 

다시 인덱스대로 정렬해야 하기때문에, 초기 입력받을 때 Pair(인덱스, 값)의 형태로 입력받고

 

값을 기준으로 오름차순 정렬하고 넘버링을 한 후에 다시 인덱스를 기준으로 오름차순 정렬을 하면 됩니다.

 

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

#define idx first
#define val second

using namespace std;

using PAIR = pair<int, int>;

const int MAX = 1000000;

vector<PAIR> v(MAX);

bool cmpIdx(const PAIR& a, const PAIR& b)
{
    if (a.idx < b.idx) return true;
    else return false;
}

bool cmpVal(const PAIR& a, const PAIR& b)
{
    if (a.val < b.val) return true;
    else return false;
}

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

    int n; cin >> n;

    for (int i = 0; i < n; i++) {
        int t; cin >> t;
        v[i].idx = i;
        v[i].val = t;
    }

    sort(v.begin(), v.begin() + n, cmpVal);

    int cnt = 0;
    for (int i = 0; i < n - 1; i++) {
        if (v[i].val != v[i + 1].val) v[i].val = cnt++;
        else v[i].val = cnt;
    }
    v[n - 1].val = cnt;

    sort(v.begin(), v.begin() + n, cmpIdx);

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

    return 0;
}

반례

Input

5

1 2 3 4 5

Output

0 1 2 3 4

 

Input

7

-99 0 3 0 7 55 123

Output

0 1 2 1 3 4 5

 

Input

10
-253 123 415 54 0 54 -54 99 100 1

Output

0 7 8 4 2 4 1 5 6 3