좌표 압축 기법- 18870번

• 언제 사용하나? 

순위(대소)가 중요한 알고리즘에서 입력값의 개수보다 입력값의 범위가 클 때 사용.

예) 좌표의 범위는 약 40억이 넘지만 최대 입력값은 백만이다.

만약 좌표가 앞부분에 몰려있다면 나머지 부분은 불필요한 공간이라 탐색하지 않아도 된다.

좌표 압축을 통해 원하는 범위만 탐색할 수 있게 된다면 시간적,공간적으로 효율적이다. 

 

#define _CRT_SECURE_NO_WARNINGS //경고 제거
#include <stdio.h>
#include <vector>
#include<algorithm>

int main() {
	int N,input;
	std::vector<int> x1,x2; //int 범위: -20억 ~ 20억 정도
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &input);
		x1.push_back(input); //정렬,중복제거할 벡터
		x2.push_back(input); //기존 벡터
	}
	/*오름차순 정렬*/
	std::sort(x1.begin(), x1.end()); 
    
	/*내 인덱스가 곧 출력값이므로 중복되면 인덱스가 밀리니 중복 제거*/
	x1.erase(std::unique(x1.begin(), x1.end()), x1.end());
    
	/*정렬된 벡터 중에서 내 인덱스가 몇번째인지 출력하기*/
	int output;
	for (int i = 0; i < N; i++) {
		output=std::lower_bound(x1.begin(), x1.end(), x2[i]) - x1.begin(); 
		/*출력 순서는 기존 벡터 순으로 해야 하므로 3번째인자는 기존벡터의 원소로 지정
		->그래서 x2만들어서 저장한거임.*/
		printf("%d ", output);
	}
	return 0;

}