문제

문제 링크

해설

• 수첩1과 2가 각각 최대 길이가 100만이므로 가장 쉬운 방법인 O(N²) 방법 (각 수첩2의 요소마다 수첩1을 처음부터 끝까지 탐색하는 방법)을 사용하면 안 됩니다.
• std::binary_search() 함수를 연습하는 문제입니다.
• 먼저, 이분탐색을 사용하기 앞서 수첩1의 모든 내용을 std::sort()로 오름차순 정렬합니다.
• 그 뒤 수첩2의 모든 내용을 std::binary_search()로 찾은 뒤 결괏값을 출력하면 됩니다.
• 정렬에 O(Nlog₂N), 탐색에 O(log₂N)이 소요됩니다.

코드

1. STL 사용

#include <bits/stdc++.h>
using namespace std;

array<int, 1'000'001> note;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int T;
	cin >> T;
	while (T--) {
		int N;
		cin >> N;
		for (int i = 0; i < N; ++i) cin >> note[i];
		
		sort(begin(note), begin(note) + N);
		
		int M;
		cin >> M; 
		for (int i = 0; i < M; ++i) {
			int num;
			cin >> num;
			cout << binary_search(begin(note), begin(note) + N, num) << '\n';
		}
	}
}

2. STL 미사용

#include <bits/stdc++.h>
using namespace std;

int T, N, M;
array<int, 1'000'001> note;

bool check(int num) {
	int l = 0, r = N - 1, m;
	while (l <= r) {
		m = l + (r - l) / 2;
		if (note[m] > num) r = m - 1;
		else if (note[m] < num) l = m + 1;
		else return true;
	}
	return false;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> T;
	while (T--) {
		cin >> N;
		for (int i = 0; i < N; ++i) cin >> note[i];
		
		sort(begin(note), begin(note) + N);
		
		cin >> M; 
		for (int i = 0; i < M; ++i) {
			int num;
			cin >> num;
			cout << check(num) << '\n';
		}
	}
}

소스코드 링크

결과