[C++] 백준 13단계 - 18870번 문제 (좌표 압축)

문제설명

 

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false); //표준 스트림 동기화 해제
	cin.tie(NULL); //입력과 출력 연결 끊기
	vector<int> original, tmp;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int input;
		cin >> input;
		original.push_back(input); //원본 벡터에 입력받음
		tmp.push_back(input); //임시 벡터에 입력받음
	}
	sort(tmp.begin(), tmp.end()); //임시 벡터 정렬
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()); //임시 벡터 중복원소 제거
	for (int i = 0; i < N; ++i) cout << lower_bound(tmp.begin(), tmp.end(), original[i]) - tmp.begin() << ' '; //원본 벡터의 i번째 원소보다 작은 임시벡터를 출력
}

 

설명

1. 원본 벡터와 임시 벡터에 모두 입력을 받음
2. 임시 벡터 정렬(sort 함수 이용)
3. 임시 벡터의 중복 원소를 제거한다.
   
   • unique(tmp.begin(), tmp.end()) -> 중복된 원소를 뒤로 밀어버려서 벡터 뒤엔 중복된 원소만 남게됨. 이후 중복된 원소의 첫 번째 원소의 주소를 리턴
     tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end()) -> 중복된 원소의 첫 번째 부터 벡터의 마지막까지를 지워버림
4. 원본벡터[i] 보다 작은 임시 벡터의 개수를 출력
   
   • lower_bound() 함수는 순차 탐색이 아니라 이진 탐색이기 때문에 정렬이 되어 있어야하고, 때문에 속도가 순차 탐색보다 훨씬 빠르다.