18870 좌표 압축(c++)

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

18870번: 좌표 압축

<코드>

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	vector<int>v;
	vector<int>v2;
	for(int i=0;i<n;i++)
	{
		int num;
		cin>>num;
		v.push_back(num);
		v2.push_back(num);
	}
	sort(v2.begin(),v2.end());
	v2.erase(unique(v2.begin(),v2.end()),v2.end());
	for(int i=0;i<v.size();i++)
	{
		cout<<lower_bound(v2.begin(),v2.end(),v[i])-v2.begin()<<' ';
	}
	

	
}

<풀이 과정>

문제를 풀기 위해 lower_bound, upper_bound가 사용되어야 한다.

lower_bound(배열의 첫번째 주소(v.begin()), 배열의 마지막 주소(v.end()),찾을 값 value)

찾을 값을 발견 하게되면 각각의 함수가 찾은 값(value)의 주소를 반환한다.

처음 value값을 만나게 되는 인덱스의 주소를 반환한다는 의미이다.

upper_bound(배열의 첫번째 주소(v.begin()), 배열의 마지막 주소(v.end()),찾을 값 value)

찾을 값을 발견 하게되면 각각의 함수가 찾은 값(value)의 주소를 반환한다.

value값보다 커진 값의 첫 번째 인덱스의 주소를 반환한다는 의미이다.

 

주소를 반환하기에 첫 번째 인덱스의 주소를 빼주면 인덱스만 반환할 수 있게 된다.

ex) lower_bound(v2.begin(),v2.end,v[i])-v2.begin()