[C++] 백준 18870 - 좌표 압축

백준 18870-좌표압축

문제

코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int n;
	int input;
	vector<int> v;
	vector<int> sv;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> input;
		v.push_back(input);
		sv.push_back(input);
	}

	sort(sv.begin(), sv.end());
	sv.erase(unique(sv.begin(), sv.end()), sv.end()); 

	for (int i = 0; i < n; i++) {
		cout << lower_bound(sv.begin(), sv.end(), v[i]) - sv.begin() << " ";
	}
}

해설

이 문제를 해결하기 위해 해야할 것은 정렬과 중복을 제거 하는 것이다.

정렬을 해야하고 출력할 때 입력한 순서대로 좌표 압축의 값을 출력해야하기 때문에 두개의 벡터를 설정했다.
중복을 제거하기 위해서는 erase와 unique를 사용하였다.

그리고 좌표압축 값을 출력하기 위해 해당 값이 정렬한 벡터에서 어느 인덱스에 위치해 있는지 알 필요가 있었는데,
이것을 알기 위해 lower_bound를 이용하였다.