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

게시 2026/04/18

By kdHyeok

5 분읽는 시간

정렬 값 / 좌표 압축

문제

문제 링크

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

문제 조건

목표: 각 좌표 Xi에 대해 Xi보다 작은 서로 다른 좌표의 개수를 구하여 좌표 압축을 수행한다.
입력 상태: N은 최대 1,000,000이며, 각 좌표는 정수 범위 내의 값을 가진다.
핵심 조건: 압축된 값은 ‘자신보다 작은 서로 다른 좌표의 개수’여야 하므로, 입력 데이터에서 중복을 제거하고 정렬된 상태에서의 인덱스를 구해야 한다.

풀이

핵심 알고리즘

정렬

시간 복잡도: O(N log N) — 정렬에 O(N log N), N번의 이분 탐색에 O(N log N)이 소요되어 총 10^6 규모의 연산을 안정적으로 처리한다.

핵심 아이디어

원본 순서를 유지하기 위해 배열 a를 별도로 관리하면서, 벡터 v에 모든 값을 담아 정렬 및 중복 제거를 수행한다. 중복이 제거된 정렬 상태에서 특정 값의 인덱스는 곧 그 값보다 작은 원소의 개수임을 이용하여 이분 탐색으로 결과값을 도출한다.

① 원본 데이터 백업 및 보조 컨테이너 활용

좌표 압축 결과를 출력할 때 입력받은 순서대로 출력해야 하므로 원본 데이터를 배열 a에 저장한다. 동시에 정렬과 중복 제거 연산을 수행하기 위해 별도의 벡터 v에 동일한 데이터를 추가한다.

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

② 정렬 및 unique-erase를 이용한 중복 제거

좌표 압축의 정의인 ‘자신보다 작은 서로 다른 좌표의 개수’를 구하기 위해 데이터를 오름차순 정렬한다. 이후 unique 함수로 인접한 중복 원소를 뒤로 보내고 erase로 삭제하여, 벡터 내의 모든 원소가 서로 다른 값을 가지도록 만든다. 이 과정을 거치면 벡터 내의 인덱스가 곧 ‘자기보다 작은 원소의 개수’가 된다.

  
  //오름차순 정렬
  sort(v.begin(), v.end());
  // 중복요소 제거
  v.erase(unique(v.begin(), v.end()), v.end());

③ lower_bound를 이용한 인덱스 검색

원본 배열 a를 순회하며 각 원소가 정렬된 벡터 v의 어느 위치(인덱스)에 있는지 이분 탐색(lower_bound)으로 찾는다. v에는 중복이 없는 상태이므로, 반환된 반복자에서 시작점(v.begin())을 뺀 값(idx)이 곧 해당 원소보다 작은 서로 다른 값의 개수가 되어 최종 결과값이 된다.

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

성능

메모리 : 12204 KB
시간 : 448 ms

코드 (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 << " ";
  }
}

algorithm