[백준/c++] 2776 암기왕

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

가장 먼저 생각해볼 수 있는 방법은 2중 for문이다. 

하지만..각각의 수첩1과 수첩2의 범위가 최대 1,000,000이기 때문에 시간초과가 된다. 

 

그러면 생각할 수 있는 방법은 두가지이다. 

첫째, 이분탐색

둘째, 해시를 사용하는 것이다. (set)

 

나는 이 중 이분탐색을 이용해서 풀었다. 

binary_search를 사용해서 그냥 풀어도 되지만 오랜만에 이분탐색을 풀어봤기 때문에 직접ㅂ 함수를 만들어서 풀어봤다. 

코드를 보면 알 수 있듯이 이분탐색을 위해서는 가장 먼저 오름차순 정렬을 해야한다. 

그 후, left, right, mid 값을 설정한 후 target값과 비교하면서 계산해주면 된다. 

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

bool binarySearch(vector<int>& arr, int target) {
	int left = 0;
	int right = arr.size() - 1;

	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] == target) {
			return true;
		}
		if (arr[mid] < target) {
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
		}
	}
	return false;
}

int main() {
	int n;
	cin >> n;
	for (int k = 0; k < n; k++) {
		vector<int> numberOne;
		vector<int> numberTwo;

		int a, b;
		cin >> a;
		for (int i = 0; i < a; i++) {
			int x;
			cin >> x;
			numberOne.push_back(x);
		}
		cin >> b;
		for (int i = 0; i < b; i++) {
			int x;
			cin >> x;
			numberTwo.push_back(x);
		}
		sort(numberOne.begin(), numberOne.end());
		//이분탐색
		for (int i = 0; i < numberTwo.size(); i++) {
			if (binarySearch(numberOne, numberTwo[i])) {
				cout << "1" << '\n';
			}
			else
			{
				cout << "0" << '\n';
			}
		}
	}
}