백준 18870번 - 좌표 압축

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

18870번: 좌표 압축

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

using namespace std;

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

	int n;
	cin >> n;
	vector<int> v;
	vector<int> copy;
	int temp;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		v.push_back(temp);
		copy.push_back(temp);
	}
	sort(copy.begin(), copy.end());
	copy.erase(unique(copy.begin(), copy.end()), copy.end());

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

중복되는 값은 세지 않아야하기 때문에, vector에서 중복된 값들을 지워줘야한다.

이를 해결하기 위해, erase() 와 unique()메소드를 활용했다.

unique() 메소드의 경우, 시작지점과 끝지점을 주면, vector의 끝부분으로 그 값들을 뒤로 옮겨주고
erase 기능을 활용해서, 해당 지점들을 삭제해주었다.

 

그리고 lower_bound를 활용한 이유는, 단순히 이중 for문을 활용하면 시간 복잡도로 인해서 
시간 초과가 된다.