[BOJ 18870] 좌표 압축

 

 

문제 링크

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

18870번: 좌표 압축

 

---

아이디어

 

'좌표압축' 기법은 PS에서 종종 쓰이는 기법으로,

큰 범위의 값을 갖는 좌표들을 정렬하여 다시 순서를 부여함으로써, 더 작은 범위 내로 압축 시키는 것이다.

 

가령 1차원 x축 위의 [1, 1e9] 의 값을 갖는 어떤 1만 개의 좌표를 생각해보자.

count[t] = x축의 값이 t인 좌표의 개수라고 할 때,

t = [1, 1e9]인 좌표의 개수를 저장하기 위해 필요한 최소의 count 배열의 크기는 1e9이다.

하지만, 1e9 + 1개의 칸중에서 실제로 사용하는 칸은 오직 1만 개이며, 나머지 빈칸은 사용하지 않는다.

이 사이사이의 비어있는 칸을 없애는 것이 좌표압축의 아이디어이다.

 

실제 좌표의 개수는 1만개이기 때문에, 좌표값의 대소비교를 통해 순서를 부여할 수 있다면,

오직 최대 1만개의 배열크기로 이를 해결할 수 있다.

 

 

아래에 소개하는 문제에서 좌표압축을 구현하기 위한 방법 중 1은 간단히 설명하고 실제 코드는 2로 보겠다.

1. stl의 map을 이용한 방법

  - 주어진 x 좌표들을 오름차순으로 정렬한다. (기존 x좌표 순서는 그대로 다른 배열에 copy)

  - cnt = 0부터 시작하여, 작은 x[i]부터 보면서

    map에 없다면 map[x[i]] = cnt++

    map에 있다면 map[x[i]] = cnt

  - 기존 x좌표의 순서대로 x값을 읽어오며 map[x[i]]의 값을 출력한다.

 

2. binary search, vector의 erase() + unique()를 이용한 방법

 기존의 x좌표들을 vector에 담아 오름차순으로 정렬하면

중복되는 x값이 없다고 가정했을 때 해당 x값을 담고 있는 vector의 index가 압축된 좌표가 된다.

 

예를 들어 문제에서 x = { 1000, 10, 100, 1, 10000}일 때,

이를 vector v에 담아서 오름차순으로 정렬하면 v = {1, 10, 100, 1000, 10000} 이고,

1의 압축된 좌표는 0,  10의 압축된 좌표는 1, 100의 압축된 좌표는 3 ... 이런 셈이다.

 

따라서 x의 값을 copy하여 vector에 담고, 이를 정렬해 정렬되지 않은 기존 x의 값을 하나하나 binary search를 통해 찾을 수 있다.

하지만 문제는, x의 값들이 중복해서 존재하는 것이고 binary search를 사용하기 위해 중복된 원소를 제거해야한다.

어떻게 하면 {0, 0, 1, 2, 3, 3, 4, 5, 5,} 와 같은 vector에서 중복된 원소를 없애 {0, 1, 2, 3, 4, 5}로 만들 수 있을까?

 

 

vector의 erase와 unique를 사용하면 간단하게 중복된 원소를 처리할 수 있다.

 

vcetor의 unique(first, last)는 정렬된 vector에서 중복된 원소(쓰레기 값)를 정렬된 데이터의 뒤로 보내고, 정렬된 데이터의 마지막 iterator의 다음 위치를 반환한다.

예를 들어, {1, 2, 2, 3, 3, 5, 6}의 vector는 unique를 통해 {1, 2, 3, 5, 2, 3, 6} 으로 바뀌고

정렬된 데이터의 마지막 원소인 5의 다음 위치인 2에 해당하는 iterator를 반환한다.

 

vector의 erase(first, last)는 vector의 first부터 last까지의 원소를 지워준다.

따라서 정렬된 v를 v.erase( unique(v.begin( ), v.end( )), v.end( ) )를 통해서 중복된 원소를 제거 할 수 있고,

binary search를 통해 기존 x의 압축된 index를 구할 수 있다.

---

소스코드

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

int n;
vector <int> x, y;
int main()
{
    scanf("%d", &n);
    x.resize(n);
    y.resize(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x[i]);
        y[i] = x[i];
    }
    sort(y.begin(), y.end());
    unique(y.begin(), y.end());
    y.erase(unique(y.begin(), y.end()), y.end());

    for (int i = 0; i < n; ++i) {
        int pos = lower_bound(y.begin(), y.end(), x[i]) - y.begin();
        printf("%d ", pos);
    }
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 언제나 부드럽게 알려주세요.