좌표 압축(Coordinate compression)

좌표의 범위가 너무 큰 경우 인덱싱으로 좌표 사이 갭을 없애는 좌표압축 기법(Coordinate compression)을 사용해 문제를 해결할 수 있습니다.

 

예를 들어 일차원 직선상에 N=10만개의 점이 있고, [x, y] 구간의 점 개수를 출력하는 쿼리가 M개 있다고 해보겠습니다.

점이 존재하는 범위가 \([1, 10^5]\)라고 하면 세그먼트 트리 등을 사용해서 O(lgn)의 시간복잡도로 처리할 수 있습니다.

 

그런데 점의 범위나 x, y의 범위가 \([-10^9, 10^9]\)라면 세그먼트 트리를 구성하려고 했을 때 일반적으로 문제에서 주어지는 메모리 256MB로는 택도 없습니다.

 

여기서 점의 개수에 비해 점의 범위가 훨씬 넓어 sparse 하다는 걸 알 수 있는데요, 이를 이용해 각 점의 좌표마다 인덱싱을 해 정렬된 순서로 번호를 매기면 답을 구할 수 있습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> idx(n);
  vector<int> points(n);
  for (int i = 0; i < n; ++i) {
    cin >> idx[i];
    points[i] = idx[i];
  }

  sort(idx.begin(), idx.end());
  idx.erase(unique(idx.begin(), idx.end()), idx.end());

  for (auto& c : points) {
    cout << lower_bound(idx.begin(), idx.end(), c) - idx.begin() << ' ';
  }
  
  return 0;
}

예제입니다.

백준 18870 좌표압축 문제인데요, C++ STL로 쉽게 풀 수 있습니다.

sort, unique, lower_bound를 사용했습니다.