[Baekjoon] 18870번: 좌표 압축 (Silver) - C++ 풀이

정렬 값 / 좌표 압축

💾 메모리: 12204 KB, 시간: 448 ms📅 2026년 2월 24일 01:16:44

문제 링크

문제 설명

수직선 위에 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 n;
int a[1000001];
vector<int> v;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    v.push_back(a[i]);
    }
  //오름차순 정렬
  sort(v.begin(), v.end());
  // 중복요소 제거
  v.erase(unique(v.begin(), v.end()), v.end());
  for(int i = 0; i < n; i++) {
    int idx= lower_bound(v.begin(), v.end(), a[i])-v.begin();
    cout << idx << " ";
  }
}