[백준]수 찾기

유의할점

시간 복잡도

풀이

일반적으로 하나하나 찾게 되면 O(NM)이므로 1억을 넘는다.

정렬후 이분 탐색으로 찾으면 MlogN이므로 시간안에 풀수있다.

코드

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

	int N;
	cin >> N;
	vector<int> arr(N);
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	sort(arr.begin(), arr.end());
	int M;
	cin >> M;
	for (int i = 0; i < M; i++) {
		int _;
		cin >> _;
		int idx = lower_bound(arr.begin(), arr.end(), _) - arr.begin();
		int res = 0;
		if (idx != arr.size()&&arr[idx] == _)
			res = 1;
		cout << res << "\n";
	}
}