문제
수직선 위에 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
Unique 함수
unique 함수는 연속으로 중복되는 원소를 vector의 제일 뒷 부분 쓰레기 값으로 보낸다.
즉, 중복 되지 않는 원소들 만을 앞에서 부터 채운다.
이때 주의할 점은 연속으로 중복되는 원소만을 없애기 때문에 반드기 정렬을 시행해 줘야 한다.
예
예를 들어 아래와 같이 정렬된 벡터 v가 있다고 쳐보자
1 2 2 3 4 4 5
unique(v.begin(), v.end())
⇒ 1 2 3 4 5
⇒ 1 2 3 4 5 4 5
⇒ 1 2 3 4 5 4 5 (노랑이 주소 반환)
v.erase(unique(v.begin(), v.end()), v.end());
⇒ 1 2 3 4 5
문제 이해
⇒ 좌표 압축이란, 현재 값에서 현재 값을 현재 값보다 작은 값들의 개수로 바꿔주는 것이다.
2 4 -10 4 -9
→ -10 -9 2 4 4
⇒ 2 3 0 3 1 (-10보다 작은 수 0개, 2보다 작은 수 2개)
※ lower_bound(시작값, 종료값, 찾는값): 찾는 값보다 같거나 큰 값을 리턴해주는 함수
이때 리턴값이 iterator이므로 .begin()을 해주면 인덱스를 리턴해준다.
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main() {
int N;
cin >> N;
long long tmp;
vector<long long> v1; // 정렬 벡터
vector<long long> v2; // 원본 벡터
for (int i = 0; i < N; i++) {
cin >> tmp;
v1.push_back(tmp); //정렬
v2.push_back(tmp);
}
sort(v1.begin(), v1.end());
v1.erase(unique(v1.begin(), v1.end()), v1.end()); // 중복값 제거
for (int i = 0; i < N; i++) {
cout << lower_bound(v1.begin(), v1.end(), v2[i]) - v1.begin() << " ";
}
return 0;
}
원본과 정렬 벡터를 따로 만들어 두고 정렬벡터 정렬하고 unique함수 써서 중복값 제거해주고,
lower_bound 함수에 원본벡터를 이용해서 몇번째로 큰지 구해주면 된다.