[백준 18870] 좌표 압축

🔗문제 풀러가기
단계별로 풀어보기 단계 13의 11번째 문제이다.

문제 분석

unique함수와 lower_bound을 함수를 활용하여 문제를 해결하였다.

코드

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

int main()
{
	int n;

	cin >> n;

	vector<int> vec;
	vector<int> vec2;

	for (int i = 0; i < n; i++)
	{
		long input;

		cin >> input;

		vec.push_back(input);
		vec2.push_back(input);
	}

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

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

해석

1. 수를 입력받아 정렬될 벡터 vec과 입력받은 순서대로 저장될 벡터 vec2에 저장한다.
2. vec를 sort를 이용해 정렬한다.
3. unique를 이용해 중복되는 것들을 지워준다.

   unique(x,y)함수는
   x부터 y까지 중복된 값이 나온 값을 하나 빼고 나머지는 맨뒤로 보낸 후 그 인덱스를 리턴하는 함수이다

4. 그후 lower_bound을 이용해 수를 출력하면 끝!

   lower_bound(시작값, 종료값, 찾는 값) 함수는
   찾는 값보다 같거나 큰 값을 리턴해주는 함수이다.
   lower_bound(vec.begin(), vec.end(), vec2[i]) - vec.begin()을 해주면
   vec에서의 vec2[i]의 위치이다.