[이진탐색] BOJ 10815 숫자카드 문제 해설

백준 BOJ(10815)

www.acmicpc.net/problem/10815

10815번: 숫자 카드

 

숫자 카드중에 가지고 있는 카드가 있다면 1 아니면 0을 출력해주는 그런 문제입니다. 이진탐색만 알면 바로 풀 수 있는 그런 문제입니다.  이진탐색에 관한 내용은 아래를 참고하시기 바랍나다.

reakwon.tistory.com/60

[알고리즘] 그림을 통한 이진탐색(Binary Search) 개념과 C 코드구현

풀이

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int n, m;
int mine[500001];
int binarySearch(int left, int right, int num) {
	if (left == right) return mine[left] == num;
	int mid = (left + right) / 2;
	if (mine[mid] == num) return 1;
	if (mine[mid] > num)
		return binarySearch(left, mid, num);
	return binarySearch(mid + 1, right, num);
}
int main() {
	scanf("%d",&n);
	for (int i = 0; i < n; i++)
		scanf("%d",&mine[i]);
	sort(mine, mine + n);
	scanf("%d",&m);
	for (int i = 0; i < m; i++) {
		int card;
		scanf("%d",&card);
		printf("%d ",binarySearch(0,n-1,card));
	}
	printf("\n");

	return 0;
}

 

탐색을 위해 문제의 입력을 갖고 있는 카드를 우선 정렬합니다. 위 코드가 해답인 코드입니다. 그리고 난 후 이진탐색으로 그 카드의 인덱스가 있는지 확인하는 방법으로 카드가 있는지 아닌지 확인할 수 있습니다.