백준 BOJ(10815)

www.acmicpc.net/problem/10815

 

10815번: 숫자 카드

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

 

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

reakwon.tistory.com/60

 

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

이진탐색 배열에서 어떤 원소를 찾을때 그 원소가 있는지 어떻게 찾을 수 있을까요?b가장 간단한 방법은 아무래도 for루프를 실행하면서 하나하씩 일치하는지 검색하는 방법이겠죠? 너무 쉽습니

reakwon.tistory.com

풀이

 

#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;
}

 

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

반응형
블로그 이미지

REAKWON

와나진짜

,