[C/C++] 백준 - 18870번 : 좌표 압축

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

18870번: 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

이분 탐색을 응용한 기법 lower_bound를 사용해야한다는 것은 문제 설명을 읽으면 알 수 있지만 하나 주의해야할 점이 서로 다른 좌표의 개수와 같아야 한다는 것이다. 이 부분은 C++ algorithm 헤더 파일이 제공하는 unique함수를 통해 해결 할 수 있다.

 

vector에 만약 {1, 2, 3, 3, 3}이 있다고 하면 3이 중복된 수가 된다. 만약 중복된 수 하나만 남기고 모두 지우고 싶다면

erase함수와 unique함수를 이용해 지울 수 있다.

v.erase(unique(v.begin(), v.end()), v.end());

위 처럼 표현을 하게 되면 unique함수가 v에 존재하는 원소 중 중복되지 않는 수만 모두 확인한 후, 앞으로 데려온다. 그리고 중복되는 수는 모두 뒤로 밀려나게 하는데, 그 밀려나게 하는 부분을 시작지점으로 그리고 마지막 부분까지 삭제하게 되면 중복되는 원소는 모두 삭제 되는 것이다. 

 

그리고 만든 v 벡터에서 lower_bound로 개수를 확인하는 것이다

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
#define ENDL cout << endl;
#define endl '\n'
#define swap(type, x, y) do{type t=y;y=x;x=t;}while(0)
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;

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

	int N;
	cin >> N;
	vector<int> v, s, Answer;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		v.push_back(x);
		s.push_back(x);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for (int i = 0; i < s.size();i++) cout << lower_bound(v.begin(), v.end(), s[i]) - v.begin() << " ";

	return 0;
}