백준 18870번:좌표 압축

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

입력

첫째 줄에 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;
}