알고리즘 문제
[C/C++ 백준 18870번] 좌표수 압축 (Silver 2)
새파란 공대생
2020. 8. 24. 23:36
https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
이분 탐색을 배우고 있어서,,, 이분 탐색을 이용해서 풀었다.
모든 원소를 배열로 받고, 그 원소들을 벡터에 넣어준 뒤 중복되는 원소들을 제거해준다. 그리고 lower_bound를 이용해 각 원소보다 작은 원소들의 개수를 찾아 출력해주자.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
long long int Num[1000001];
int main(void){
int N;
vector <long long int> v;
vector <long long int>::iterator iter;
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%lld", &Num[i]);
v.push_back(Num[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i=0; i<N; i++){
printf("%lld ", lower_bound(v.begin(), v.end(), Num[i]) - v.begin());
}
}