[BOJ/C++] 숫자 카드(10815번)

1. 개요

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

10815번: 숫자 카드

1-1. 설명

숫자 카드는 정수 하나가 적혀있는 카드다. 상근이는 숫자카드 N개를 지니고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 지니고 있는지 아닌지 구하는 프로그램을 작성한다

1-2. 제한 사항

 - 첫 줄에는 상근이가 지니고있는 숫자 카드 개수 N이 주어짐

 - N은 1 이상 500,000 이하 자연수

 - 둘째 줄에는 숫자 카드에 적힌 정수가 주어짐

 - 숫자 카드에 적혀있는 수는 -10,000,000 이상, 10,000,000 이하이며, 두 숫자 카드에 같은수가 적혀있는 경우는 없음

 - 셋째 줄에는 M이 주어지며, M 또한 1 이상 500,000 이하 자연수

 - 넷째 줄에는 숫자 카드에 적힌 정수가 주어지며 둘째줄과 동일한 범위를 지님

---

2. 구현

2-1. 풀이

모든 숫자를 탐색하여 풀면 시간 초과가 날 것을 예상해서 다른 방법을 생각했었다. 이진 탐색을 이용하면 제한 시간 내에 찾는 것이 가능하다. 

2-2. 코드

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

int binarySearch(int val, int first, int last);
constexpr size_t MAX_NUM = 500000;
int nums[MAX_NUM];
int result[MAX_NUM];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, num;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		nums[i] = num;
	}
	sort(nums, nums + N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> num;
		result[i] = binarySearch(num, 0, N-1);
	}

	for (int i = 0; i < M; i++) {
		if (result[i] == -1) cout << "0 ";
		else cout << "1 ";
	}
	return 0;
}
        
int binarySearch(int val, int first, int last) {
	if (first > last) return -1;
	int mid = (first + last) / 2;
	if (val == nums[mid]) return mid;
	else if (val < nums[mid]) return binarySearch(val, first, mid - 1);
	else return binarySearch(val, mid + 1, last);
}