[BOJ] 18870 좌표 압축

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

18870번: 좌표 압축

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

sort

 

---------------------------------------------------풀이----------------------------------------------------

 

각 Xi에 대해, 다른 좌표의 값들 중 자신보다 작은 값이 몇 개 있는지를 출력하는 문제이다.

따라서, 실제 값(Xi)과 인덱스(i)를 pair로 묶어 실제 값을 기준으로 오름차순 정렬하였다.

그 다음, 정렬된 벡터를 앞에서부터 확인하면서, answer[i]에 정렬된 벡터에서의 인덱스(즉, 몇 번째로 작은가)를 저장하였다.

이렇게 할 경우, 같은 값을 가진 경우가 문제가 된다.

예를 들어, 2 4 -10 4 -9를 정렬하면

(실제 값, 원래 인덱스)

(-10, 2) (-9, 4) (2, 0) (4, 1) (4, 3)이 되는데

네 번째와 다섯 번째 값이 같으므로 answer[3] = 3이 답이지만, answer[3] = 4가 된다.

따라서 이 케이스에 대한 예외 처리를 위해, 앞에서부터 같은 개수를 세어 same으로 저장하였다.

정렬된 인덱스대로 저장해줄 때, 

(4, 3)의 경우 answer[3] = 4-same(1) = 3으로 정상적으로 저장되는 것을 알 수 있다.

다시 말해, (4, 3)은 4번째로 작은 수처럼 보이지만 앞에 같은 수가 하나 있어 same 개수를 뺀 3번째로 작은 수로 처리된다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;


// X'i = Xi > Xj를 만족하는 서로 다른 좌표의 개수. 즉, 자신보다 작은 개수
int main(void){
    FASTIO;
    int N;
    cin >> N;
    // 실제 값, 원래 인덱스
    pair<int,int> Xi[1'000'001];
    for(int i = 0; i < N; i++){
        cin >> Xi[i].first;
        Xi[i].second = i;
    }
    sort(Xi, Xi+N);
    vector<int> ans(N);
    // 같은 값을 가진 앞의 인덱스들의 개수
    int same = 0;
    for(int i = 0; i < N; i++){
        ans[Xi[i].second] = i - same;
        if(i < N-1 && Xi[i].first == Xi[i+1].first){
            same++;
        }
    }
    for(int i = 0; i < N; i++){
        cout << ans[i] << " ";
    }
    cout << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

정렬을 이용한 문제.