[알고리즘] 좌표 압축

좌표 압축

❓좌표 압축이란

수의 범위가 매우 큰 상태에서 수의 값과 상관 없이 숫자 간의 대소관계만 알면 될 때 이용하는 알고리즘이다.

✔️ 활용 방법

기본적으로 해당 알고리즘은 정렬, 이분 탐색을 이용한다.

• STEP 1 : 입력받은 배열과 별도의 배열을 하나 선언한다.
  이때, 이 별도의 배열을 '압축 배열'이라고 명명하겠다. 해당 압축 배열에 입력받은 배열에 대해 오름차순 정렬한다.

vector<int> v; //별도의 배열 하나 선언
sort(v.begin(), v.end()); //오름차순 정렬

• STEP 2 : 압축 배열의 중복 요소를 제거한다.

v.erase(unique(v.begin(), v.end()), v.end()); //중복 요소 제거

• STEP 3 : 이제 입력 배열의 요소값과 같은 압축 배열의 요소값을 탐색한다. 탐색에 성공하면(같으면), 해당 위치의 인덱스를 출력한다.

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

💡 문제를 풀어보자!

문제 풀러 바로가기 >> 18870 :: 좌표 압축

💻 정답 코드

#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 << " ";
  }
}