[3] 좌표 압축 (Coordinate-Compression)

좌표 압축은 PS에서 정말 많이 쓰이는 테크닉으로, 세그트리 같이 구간 쿼리를 해결하기 위해 많이 사용한다.

세그트리는 주어진 범위의 모든 영역을 Leaf node로 사용하기 때문에, 해당 범위가 커지면 좌표 압축이 필요하다.

 

결국 좌표 압축은, 해당 좌표를 0,1,2 ~ 의 값으로 치환하는 것인데, 

그 자체는 매우 어렵고 이해가 되지 않는 개념은 아니다. 

 

for (int i = 0; i < n; i++)
{
  cin >> comp[i];
  v.push_back(comp[i]);
}

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

v.resize(unique(v.begin(), v.end()) - v.begin());

for (int i = 0; i < n; i++)
{
  comp[i] = lower_bound(v.begin(), v.end(), comp[i]) - v.begin();
  cout << comp[i] << ' ';
}

 

모든 입력을 받았으면 우선 배열과 벡터에 넣는다

벡터는 나중에 "인덱스의 레퍼런스"로 지정될 것이고

배열은 실제 데이터가 저장될 것이다.

 

sort를 이용해 소팅하면 1112222 이런식으로 되는데

이제 unique 연산 후 반환되는 포인터 구간 까지로 resize하면 정렬된 unique한 입력값들을 얻을 수 있다.

그럼 이제 기존 값을 벡터의 매칭되는 인덱스 값으로 지정해주면 된다. 

lower_bound는 이분 탐색을 하므로 전체 복잡도는 nlogn이다. 

 

알고리즘 고수 친구에게 항상 감사히 많이 배우고 있다. 

열심히 해야지~