[BOJ/18870/C++] 좌표 압축

문제출처:https://www.acmicpc.net/problem/18870

문제

• 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
• Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
• X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

조건

• 1 ≤ N ≤ 1,000,000
• -10^9 ≤ Xi ≤ 10^9

풀이

좌표압축은 알고리즘에서 꽤 흔히, 자주쓰이는 개념이다. 좌표의 실제 값보다, 순서가 더 중요하고 순서만을 따지고 싶을 때 쓸 수 있는데 이거에 대해서는 따로 글을 적어야할 것 같다. 분량이 생각보다 꽤 된다.

간단하게 요약하면, 중복이 있다면 제거하고 정렬했을 때, 자기가 몇번째 순서인지 보면된다.

중복을 제거하는 방법도 unique함수를 이용해서 중복을 다 제거한 뒤 끝의 주소값을 반환받은 뒤 erase함수를 이용하는 방법도 있지만, 새로운 공간을 하나 만들어서 이전과 같은값이면 넘어가는 형식으로 만들 수도 있다.

값 -> 인덱스

값에서 인덱스를 거슬러 올라가는게 생각보다 까다로울 수 있는데, 우리가 배운 lower_bound를 이용하면 쉬워진다. 제일 처음 등장하는 주소값을 알게되고, 배열이나 vector같은 연속적인자료공간을 갖는 STL은 시작주소를 빼주면 해당 인덱스가 뿅하고 나오게 된다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int N;
int arr[1000005];
int main()
{
  fastio;
  cin >> N;
  vector<int> tmp;
  vector<int> uni;
  for (int i = 0; i < N; i++)
  {
    cin >> arr[i];
    tmp.push_back(arr[i]);
  }
  sort(tmp.begin(), tmp.end());
  for (int i = 0; i < N; i++)
  {
    if (i == 0 || tmp[i - 1] != tmp[i])
    {
      uni.push_back(tmp[i]);
    }
  }
  for (int i = 0; i < N; i++)
    cout << lower_bound(uni.begin(), uni.end(), arr[i]) - uni.begin() << " ";
  return 0;
}