백준 10815 숫자카드

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

숫자카드를 배열에 입력받고 각카드가 들어 있는지 확인 한뒤 1 / 0을 출력하는 문제입니다.

 

그냥 배열의 앞부터 끝까지 출력하는 문제는 시간이 많이 소요되므로 배열을 정렬한뒤 이분탐색을 이용하는 문제입니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,M;
	cin >> N;
	int arr[N];
	for(int i = 0; i < N; i++)
		cin >> arr[i];
	
	sort(arr, arr+N);
	cin >> M; 
	for(int i = 0; i < M; i++) {
		int start = 0;
		int end = N-1;
		int mid;
		bool flag = true;
		int x;
		cin >> x;
		while(start <= end) {
			mid = (start + end) / 2;
			
			if(arr[mid] == x) {
				flag = false;
				break;
			}
			else if(arr[mid] < x) {
				start = mid + 1;
			}
			else if(arr[mid] > x) {
				end = mid - 1;
			}
		}
		if(flag)
			cout<<0<<' ';
		else
			cout<<1<<' ';
	}
	return 0;
}