문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
제한
1 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109

예제 입력 1

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

예제 입력 2

6
1000 999 1000 999 1000 999

예제 출력 2

1 0 1 0 1 0

풀이

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int b[1000005];
vector<int> v;
int n, mid;
int start, end;
int binarySearch(int target){ // 이분탐색 함수, 목표값을 찾으면 목표값의 index 위치를 반환한다.
	int start = 0;
	int end = v.size()-1;
	while(start <= end){
		mid = (start+end)/2;
		if(v[mid] > target){
			end = mid - 1;
		}
		else if(v[mid] < target){
			start = mid + 1;
		}
		else{
			return mid;
		}
	}
	return 0;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(a,a+n);
	v.push_back(a[0]);
	for(int i = 1; i < n; i++){
	if(a[i] != a[i-1]) v.push_back(a[i]);
	else continue;
	}   // 배열 a는 입력받은 배열을 정렬한 배열이고, b는 온전한 초기의 배열이다.
    //그리고 정렬된 배열 a를 중복을 제거하여 벡터 v에 추가한다.
	for(int i = 0; i < n; i++){
		cout << binarySearch(b[i]) << " "; // 입력값에 대하여 각각 이분탐색을 시행한다.
	}
	return 0;
}