C++) 백준 1920번 - 수 찾기

	#include<iostream>
	#include <vector>
	#include<algorithm>
	using namespace std;
	vector<int> ary;
	vector<int> ans;
	vector<int>::iterator iter;
	int search(int a, int left=0, int right=ary.size()-1){
	if(right<left){
	ans.push_back(0);
	return 0;
	}
	int middle=(left+right)/2;
	if(ary[middle]==a) ans.push_back(1);
	else if(ary[middle]>a) search(a,0,middle-1);
	else search(a,middle+1,right);
	return 2;
	};
	int main(){
	ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	int n,m,element;
	cin>>n;
	for(int i=0;i<n;i++){
	cin>>element;
	ary.push_back(element);
	}
	sort(ary.begin(),ary.end());
	cin>>m;
	while(m--){
	cin>>element;
	search(element);
	}
	for(iter=ans.begin();iter!=ans.end();iter++){
	cout<<*iter<<"\n";
	}
	}

view raw boj1920.cpp hosted with ❤ by GitHub

이원탐색(binary search)과 STL의 sort함수를 이용했다.

이원탐색은 재귀함수의 형태로 구현했고 ary vector를 통해 입력값을 받아 sort한 후 탐색을 통해 결과를 ans vector에 저장해 출력했다.