백준 코딩
백준 18870번:좌표 압축
까르르꿍꿍
2021. 9. 25. 21:01
https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
이번 문제에서 여태껏 배운 라이브러리로 해봤지만 시간초과가 나면서 힘들었다. 그러면서 찾게 된 좋은 라이브러리가 있었다. 그건 바로 unique함수와 lower_bound 함수 이다
unique(배열초기주소,배열끝주소,중복된 값 어디에다 넣을지 주소) 는 중복된 값을 빼서 뒤로 빼주는 함수이다. 반환값은 중복된값 초기 위치이다.
lower_bound(배열 주소,배열 끝주소,찾는 값) 함수는 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾는 함수이다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define PI 3.1415926535
using namespace std;
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
int n;
vector<int> x;
vector<int> y;
int k;
cin >> n;
while (n--) {
cin >> k;
x.push_back(k);
y.push_back(k);
}
sort(x.begin(), x.end()); //x값 정렬
int len = x.size();
x.erase(unique(x.begin(), x.end()), x.end()); //x중복된 값 위치부터 erase함수로 지우기
for (int i = 0; i < len; i++) {
int it;
it = lower_bound(x.begin(), x.end(), y[i])-x.begin(); //찾으려는 값 위치 주소에서 초기 주소를 뺴서 인덱스 값 구하기
cout << it << ' ';
}
return 0;
}