BOJ- 10815번

문제 설명

• 10815번, 숫자 카드

• 난이도: 실버4

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

1 ≤ N ≤ 500,000
숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

문제 해석

딱히 해석할 것이 없이 그냥 이진탐색문제이다.

아래 코드에서 주의할 점 중 하나는 find함수에서 vector를 레퍼런스로 받는다는 점이다.

만약 레퍼런스로 받지 않을 경우 복사하여 받게 되는데 이때 시간이 많이 걸려 시간초과를 받게 된다.

코드

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

bool find(vector<int>& v, int t) {
	int start = 0;
	int end = v.size() - 1;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (v[mid] > t)
			end = mid - 1;
		else if (v[mid] < t)
			start = mid + 1;
		else
			return true;
	}
	return false;
}

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

	int N;
	cin >> N;
	vector<int> m;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		m.push_back(x);
	}
	sort(m.begin(), m.end());
	
	int M;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int x;
		cin >> x;
		cout << find(m, x) << " ";
	}

	return 0;
}