[Silver / 18870] 좌표 압축

문제 링크

---

🔷 분류

정렬, 값 / 좌표 압축

✒️ 문제 설명

수직선 위에 N개의 좌표 X₁, X₂, …, X_N이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

X_i를 좌표 압축한 결과 X’_i의 값은 X_i > X_j를 만족하는 서로 다른 좌표 X_j의 개수와 같아야 한다.

X₁, X₂, …, X_N에 좌표 압축을 적용한 결과 X’₁, X’₂, …, X’_N를 출력해보자.

⬅️ 입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X₁, X₂, …, X_N이 주어진다.

➡️ 출력

첫째 줄에 X’₁, X’₂, …, X’_N을 공백 한 칸으로 구분해서 출력한다.

💻 코드 (C++)

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

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

  vector<int> sorted = A;
  sort(sorted.begin(), sorted.end());
  sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end()); // 중복 제거

  for(int i : A) {
    auto it = lower_bound(sorted.begin(), sorted.end(), i); // 정렬된 위치
    cout << it - sorted.begin() << " ";
  }
  return 0;
}