[BOJ] 18870번 좌표 압축 (C++)

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

18870번: 좌표 압축

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

	int n;
	cin >> n;
	vector<int> v(n);

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	vector<int> tmp(v);
	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

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

	return 0;
}

원본 벡터를 입력받고 원본 벡터를 복사한 벡터를 만들어 정렬한 후 unique 함수로 중복 값을 제거해준다. lower_bound 함수를 통해 원본 벡터의 i번째 원소가 복사한 벡터에서 몇 번째에 위치하는지 확인하고, lower_bound의 반환값에서 시작 주소값을 뺀 값이 답이다.

 

벡터의 크기를 지정하지 않고 for문을 돌리면 "vector subscript out of range" 오류가 발생하므로 처음 벡터를 선언할 때 크기를 n으로 지정해주어야 한다.