[백준 알고리즘] 1920번 : 수 찾기

문제

1920번 : 수 찾기

1920번: 수 찾기

내가 작성한 코드 (C++ 성공)

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
	cin.tie(NULL);
	
	int n, m;
	cin >> n;	
	int a[n+1];
	
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	
	sort(a, a+n);
	
	cin >> m;	
	int input[m+1];
		
	for(int i=0; i<m; i++){
		cin >> input[i];
		//cout << "input[" << i << "] : " << input[i] << "\n";
		
		int s = 0, e = n, mid;
		//cout << "s : " << s << " / e = " << e << " / mid : " << mid << "\n";
		
		bool check = false;
		
		while(s <= e){
			mid = (s+e)/2;
			//cout << "mid : " << mid << "\n";
			//cout << "input : " << input[i] << " / mid : " << a[mid] << "\n";
			if(input[i] < a[mid]){
				e = mid-1;
			} else if(input[i] > a[mid]) {
				s = mid+1;
			} else {
				check = true;
				break;
			}	 
		}
		if(check) cout << "1\n";
		else cout << "0\n";
	}
	
	return 0;
}

 

정리

이 문제는 이분 탐색을 이용해서 풀 수 있는 문제였다.
이분 탐색을 이용해서 풀지 않으면 시간 초과가 발생하기 때문에 이분 탐색을 이용해서 풀어야 통과할 수 있었다.
이분 탐색에 대한 개념와 알고리즘은 다시 공부를 통해 블로그에 정리해둬야겠다.