좌표 압축 (Coordinate Compression)

3년전에 대학 과제로 좌표 압축 기법을 활용하는 문제가 나왔었지만 이해를 못해서 풀지 못했습니다.

지금와서 보니 생각보다 간단했고, 정리하면서 포스팅합니다.

 

우선 좌표압축이란, 수의 범위가 크게 주어질 때 인덱스를 이용하여 범위를 줄이는 기법입니다.

코테에서 요구하는 기법은 아닐지라도 대회 준비를 하셨던 분이라면 보신 적이 있을 거라고 생각합니다.

그만큼 PS에서 많이 사용되는 기법이며, 한 번쯤 알아가는 것도 괜찮은 것 같습니다.

 

1차원 배열

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

18870번: 좌표 압축

이 문제가 가장 기본적으로 좌표 압축을 체험해볼 수 있는 문제입니다.

1차원 좌표를 압축하는 것이 문제에서 요구하는 것인데, 좌표의 범위가 -10억 ~ 10억입니다.

이 범위를 한번씩 돌며 순위를 부여하는데 너무 많은 시간이 필요합니다.

이를 해결하기 위한 기법이 좌표 압축입니다.

좌표의 범위는 -10억 ~ 10억이지만 N의 범위는 1 ~ 100만인 것을 이용합니다.

 

로직의 진행 순서입니다.

1. 우선 입력을 받을 때, 원래 배열 순서를 유지해야 하므로 인덱스도 함께 저장합니다.
2. 배열을 좌표를 기준으로 오름차순 정렬합니다.
3. 이전 값을 사용하기 위한 pre와 압축된 값을 위한 cnt 변수를 선언, 초기화합니다.
4. N만큼 for문을 돌면서 pre와 list[i] 값을 비교합니다.
5. pre == list[i]이면 이전에 등장했던 수가 있으므로 cnt를 유지합니다.
6. pre != list[i]이면 다른 수가 등장했으므로 cnt를 1 증가합니다.
7. pre를 현재 좌표값으로 갱신하고, list[i]에 cnt를 넣어줍니다.
8. 압축된 배열을 원래 배열 순서로 돌리기 위해 1번에서 저장했던 인덱스를 기준으로 오름차순 정렬합니다.

이렇게 되면

2 4 -10 4 -9

이었던 좌표가

2 3 0 3 1

이렇게 변환되는 것을 볼 수 있습니다.

 

 

이 방법 외에 unique를 이용하는 방법도 있습니다.

두 개의 벡터를 사용하며, 하나는 원래 벡터, 하나는 정렬하여 중복을 제거한 벡터로 사용됩니다.

중복을 제거한 후 lower_bound를 적용하면 원래 벡터에서 값의 순서를 알 수 있습니다.

 

원래 벡터를 w, 중복을 제거한 벡터를 v라고 했을 때,

로직의 진행 순서로는

1. 입력 받은 값을 벡터 2개에 같이 넣어줍니다.
2. 벡터 v를 오름차순으로 정렬합니다.
3. erase와 unique를 이용하여 정렬된 벡터 v에서 중복을 제거합니다.
4. N만큼 for문을 돌면서 lower_bound를 이용하여 w[i] 값의 압축된 값을 가져옵니다.

첫 번째 방법

두 번째 방법

간단해 보이지만 위의 문제에서는 첫 번째 방법이 메모리, 시간 부분에서 효율적인 것을 알 수 있습니다.

 

간단하게 소스도 첨부합니다.

 

첫 번째 방법

#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;
typedef pair<int, int> pii;
 
pii list[MAX];
int N;
 
void func() {
    sort(list, list + N);
 
    int pre = 1e9 + 1;
    int cnt = -1;
    for (int i = 0; i < N; i++) {
        if (pre != list[i].first) cnt++;
        pre = list[i].first;
        list[i].first = cnt;
    }
    sort(list, list + N, [](pii a, pii b) {
        return a.second < b.second;
    });
 
    for (int i = 0; i < N; i++) {
        cout << list[i].first << ' ';
    }
    cout << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first;
        list[i].second = i;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

두 번째 방법

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 1000000
using namespace std;
 
vector<int> v, w;
int N;
 
void func() {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
 
    for (int i = 0; i < N; i++) {
        cout << lower_bound(v.begin(), v.end(), w[i]) - v.begin() << ' ';
    }
    cout << '\n';
}
 
void input() {
    int x;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x;
        v.push_back(x);
        w.push_back(x);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}

 

2차원 배열

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

10167번: 금광

이 문제는 좌표 압축만을 요구하지는 않지만 2차원 배열 좌표압축을 해야하는 문제입니다.

세그먼트 트리처럼 구간 쿼리를 사용하는 문제에 좌표 압축을 적용할 수 있어 이 문제를 가져왔습니다.

전체 풀이는 추후 포스팅할 예정이고, 좌표 압축에 해당하는 부분만 진행하려고 합니다.

 

사실 2차원 배열 압축은 위 방법들을 그대로 사용하면 됩니다.

1차원 배열에 적용했던 것들을 두 번 적용하는 것입니다.

 

첫 번째 방법

두 번째 방법

이 문제도 첫 번째 방법이 좀더 효율적으로 나왔습니다.

두 번째 방법이 더 간단할 수 있지만 저는 첫 번째 방법을 쓸 것 같습니다.

 

이 문제는 좌표 압축 코드만 첨부합니다.

 

첫 번째 방법

void func() {
    sort(list + 1, list + 1 + N, [](Point a, Point b) {
        return a.x < b.x;
    });
 
    int pre = 1e9 + 1;
    int xCnt = 0;
    for (int i = 1; i <= N; i++) {
        if (pre != list[i].x) xCnt++;
        pre = list[i].x;
        list[i].x = xCnt;
    }
 
    sort(list + 1, list + 1 + N, [](Point a, Point b) {
        return a.y < b.y;
    });
 
    pre = 1e9 + 1;
    int yCnt = 0;
    for (int i = 1; i <= N; i++) {
        if (pre != list[i].y) yCnt++;
        pre = list[i].y;
        list[i].y = yCnt;
    }
}

 

두 번째 방법

void func() {
    sort(xtmp.begin(), xtmp.end());
    xtmp.erase(unique(xtmp.begin(), xtmp.end()), xtmp.end());
 
    sort(ytmp.begin(), ytmp.end());
    ytmp.erase(unique(ytmp.begin(), ytmp.end()), ytmp.end());
 
    for (int i = 1; i <= N; i++) {
        list[i].x = lower_bound(xtmp.begin(), xtmp.end(), list[i].x) - xtmp.begin() + 1;
        list[i].y = lower_bound(ytmp.begin(), ytmp.end(), list[i].y) - ytmp.begin() + 1;
    }
}