백준 18870번 c++ 풀이

안녕하세요 오늘은 이진탐색함수 및 정렬함수를 사용하는 문제를 풀어보겠습니다.

 

전략:

1. 두개의 벡터를 세운다(v, temp) 각각 입력을 받은 벡터, 입력받은 벡터에서 중복값을 삭제시키고 정렬한 벡터

2. 입력을 받는 for문을 세운다.

3. sort함수를 이용하여 sort를 이용하여 temp 벡터를 정렬시켜준다.

4. 정렬된 temp벡터에 erase 함수와 unique함수를 이용하여 중복을 찾아서 지워준다.

5. for문을 작성하고, 그 안에 이진탐색 방법으로 v[i]값들의 위치를 찾는 변수를 선언해서 출력해준다.

 

코드:

#include <bits/stdc++.h>
#include <vector>

using namespace std;

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

	int N;
	cin>>N;
	vector<int> v(N);
	vector<int> temp;
	for(int i = 0; i<N; i++){
		int x;
		cin>>x;
		v[i] = x;
		temp.emplace_back(x);
	}	

	sort(temp.begin(), temp.end());
	temp.erase(unique(temp.begin(), temp.end()), temp.end());
	for(int i = 0; i<N; i++){
		int ind = lower_bound(temp.begin(), temp.end(), v[i]) - temp.begin();
		cout<<ind<<" ";
	}
	

}