[C++] 백준 10815번 숫자 카드

 

1) 문제설명

 

2) 아이디어

상근이가 가지고 있는 숫자 카드를 오름차순으로 정렬하고 이분 탐색을 통해 숫자카드를 가지고 있으면 1을 출력, 가지고 있지 않으면 0을 출력한다. 기본적인 이분 탐색 알고리즘을 알고 있다면 쉽게 풀 수 있다.

printf, scanf 함수를 사용해서 시간 초과가 나지 않도록 주의한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[500001];
int brr[500001];
int search(int start, int end, int key) {
	if (start == end) {
		if (arr[start] == key) { // 시작과 끝이 같을때 키값과 같다면 1 출력 후 리턴
			printf("1 ");
			return 0;
		}
		else { // 재귀를 끝까지 돌았음에도 키값이 나오지 않았다면 0 출력 후 리턴
			printf("0 ");
			return 0;
		}
	}

	int mid = (start + end) / 2;
	if (arr[mid] >= key) { // 중간보다 키값이 작다면 앞에서 찾기
		return search(start, mid, key);
	}
	else { // 중간보다 키값이 크다면 뒤에서 찾기
		return search(mid + 1, end, key);
	}
}
int main() {
	int n, m;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr, +arr + n);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &brr[i]);
		search(0, n, brr[i]);
	}
}