좌표 압축
문제
수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 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
-10^9 ≤ Xi ≤ 10^9
1
2
3
4
5
6
7
8
9
10
11
12
13
예제 입력 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
각 X’i에 대해 자신보다 작은 수가 몇개 있는지를 보면 된다.
이 때 중복은 없어야하므로 set이나 sort, erase를 통해 정렬을 한 다음
정렬한 결과에 이분 탐색으로 값이 몇 번쨰인지 확인하면 풀 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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 << " ";
}
}
멀티버스 Ⅱ(18869, G5) 이 문제가 좌표 압축 연습으로 좋다.