[백준] 10815 숫자 카드 (C++)

 

문제 URL:

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

10815번: 숫자 카드

 

이 문제는 숫자 카드 N개가 있고 정수 M개가 주어졌을 때, 주어진 M개의 정수 중 하나와 같은 숫자가 적혀있는 숫자 카드를 가지고 있는지 아닌지를 구하는 문제이다.

이때 정수와 숫자가 같은 숫자 카드를 가지고 있으면 1을, 아니면 0을 출력해준다. 

 

처음에 문제 자체를 이해하는데 많은 시간이 걸렸다. 이 문제는 이분 탐색을 이용해 푸는 문제로 

숫자 카드를 정렬한 뒤 이분탐색을 통해 M개의 정수 중 하나와 하나씩 대조해주면 된다.

---

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

int arr1[500001];
int arr2[500001];
int n, m;

void binary_search(int n, int val) {
	int low = 0;
	int high = n - 1;

	while (low <= high) {
		int mid = (low + high) / 2;
		if (arr1[mid] == val) {
			cout << "1\n";
			return;
		}
		else {
			if (arr1[mid] > val)
				high = mid - 1;
			else
				low = mid + 1;
		}
	}
	cout << "0\n";
}

int main() {

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr1[i];

	cin >> m;
	for (int i = 0; i < m; i++)
		cin >> arr2[i];

	sort(arr1, arr1 + n);

	// 첫번째 숫자 카드 배열과 두번째 숫자 카드 배열 중 한 가지 값을 대조함 
	// (첫번째 숫자 카드 배열에 카드가 존재하는 지 확인)
	for (int i = 0; i < m; i++)
		binary_search(n, arr2[i]);

	return 0;
}