백준 18870번 "좌표 압축"

4 Jan 2022 ~ 3 Jan 2022

백준 18870번 “좌표 압축”

Question:

수직선 위에 N개의 좌표 X₁, X₂, …, X_N이 있다.
이 좌표에 좌표 압축을 적용하려고 한다.

X_i를 좌표 압축한 결과
X^’_i의 값은
X_i > X_j를 만족하는
서로 다른 좌표의 개수와 같아야 한다.

X₁, X₂, …, X_N에 좌표 압축을 적용한 결과
X^’₁, X^’₂, …, X^’_N를 출력해보자.

Input:

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X₁, X₂, …, X_N이 주어진다.

Output:

첫째 줄에 X^’₁, X^’₂, …, X^’_N을 공백 한 칸으로 구분해서 출력한다.

Restriction:

시간제한:
2 초

조건:

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

Example Case:

Input case 1:

5
2 4 -10 4 -9

Output case 1:

2 3 0 3 1

Input case 2:

6
1000 999 1000 999 1000 999

Output case 2:

1 0 1 0 1 0

풀이 과정:
좌표 압축 기법은,
다루는 데이터의 범위가 넓지만
다루는 데이터의 밀도가 낮을 때(수가 작을때),
메모리 낭비를 막기 위하여 데이터를 변환한다.
각 데이터의 좌표마다 인덱싱을 통해 정렬된 순서로 번호를 매긴다.
변환한 데이터를 이분탐색을 통하여 비교적 짧은시간(log n)안에 탐색 할 수 있다.

이 문제에 한해서 필자는 tuple을 통해 풀었지만,
(tuple <int,int,int> = (본래 데이터 / 본래 데이터 정렬 순서 / 변환 좌표 순서))
정렬 후 중복되는 값을 지우고 난 뒤
c++의 lower_bound(이분 탐색)을 통해 해당 값에 대한 인덱스를 편하게 받아 올 수 있다.
아래 코드는 lower_bound의 예시이다.
당연하게도, 이분탐색을 하려면 값들이 오름차순으로 정렬되어 있어야한다.
(*upper_bound는 찾으려는 key값을 초과하는 숫자의 첫 index 반환)

1
2
3
4
5
6
7
int arr[6] = { 1,2,3,4,5,6 };
int target = 3;
cout << lower_bound(arr,arr+6,target) - arr;
//arr 처음부터 끝까지 target값 보다 큰 숫자가 처음으로 나오는 위치의 인덱스 번호를 반환.
// lower_bound return형은 Iterator이기에, 실제로 몇 번째 인덱스인지 알고 싶다면
// lower_bound값에서 배열 첫 번째 주소를 가르키는 배열의 이름을 빼줘야한다.
// vector면 v.begin()을 빼주자.

아래의 코드는 해당 문제의 코드이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

bool cmp(tuple <int,int,int> a,tuple <int,int,int> b) {
    return get<1>(a) < get<1>(b);
}

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

    int n,temp;
    cin >> n;
    tuple <int,int,int> t1; // original value / original order / xi > xj cnt
    vector <tuple <int,int,int>> v;
    
    for(int i = 0;i<n;i++) {
        cin >> temp;
        t1 = make_tuple(temp,i,0);
        v.push_back(t1);
    }

    sort(v.begin(),v.end()); //sort ascending

    for(int i = 1;i<n;i++) { //compare only front val => sorted by first val
        if(get<0>(v[i-1]) < get<0>(v[i])) {
            get<2>(v[i]) = get<2>(v[i-1]) + 1; 
        }
        else {
            get<2>(v[i]) = get<2>(v[i-1]);
        }
    }

    sort(v.begin(),v.end(),cmp); // sort back with original order

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

}