🎲문제

주소:백준 18870

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

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

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

⌨ 입력

첫째 줄에 N이 주어진다.

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

✅ 풀이

풀이방법

두개의 벡터와 unique 함수를 사용한다. unique함수는 벡터내 중복되는 개체들을 뒤로 밀어내고, 그 주소를 반환한다.

하나의 벡터에 입력값을 모두 입력받고, 복사하여 두 개의 같은 벡터를 만든 후, 하나의 벡터를 중복 값 없이 정렬한다.(erase, unique사용) 기존 벡터의 첫 인덱스부터 마지막까지의 원소를 순차적으로 이분탐색으로 두번째 벡터의 인덱스 값을 찾아 순차적으로 인덱스 값을 반환한다.

1. N을 입력받고 벡터에 입력값을 모두 push한다.

   void init() {
   	cin >> N;
   	for (int i = 0; i < N; i++) {
   		cin >> tmp;
   		v.push_back(tmp);
   	}
   }

2. 한 개의 벡터를 더 생성해 복사하고 정렬한다.

3. erase함수와 unque함수를 통해 중복되는 값을 제거한다.

4. 이분탐색 기반인 lower_bound를 사용하여 v[0], v[1]에 해당하는 기존 벡터의 값을 정렬된 벡터 값에서 찾아 반환하여 순차적으로 출력한다.

   void solve() {
   	vector<int> v2(v);
   	sort(v2.begin(), v2.end());
   
   	v2.erase(unique(v2.begin(), v2.end()), v2.end());
   	for (int i = 0; i < N; i++) {
   		auto it = lower_bound(v2.begin(), v2.end(), v[i]);
   
   		cout << it - v2.begin() << " ";
   	}
   }

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>

using namespace std;

int N, tmp;
vector<int> v;

void init();
void solve();

void init() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}
}

void solve() {
	vector<int> v2(v);
	sort(v2.begin(), v2.end());

	v2.erase(unique(v2.begin(), v2.end()), v2.end());
	for (int i = 0; i < N; i++) {
		auto it = lower_bound(v2.begin(), v2.end(), v[i]);

		cout << it - v2.begin() << " ";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
	solve();
}