[BOJ1920] 수 찾기

[BOJ1920] 수 찾기

문제 링크

문제 설명

• 정수의 집합 A를 입력받는다.
• 그 다음 줄부터 주어지는 정수들에 대해 그 정수가 집합 A에 속해있는지를 찾는 문제이다.

코드 리뷰

• 시간 제한이 2초이고, 집합 A는 100000개까지 입력받을 수 있고, 다음 줄부터 주어지는 정수들이 최대 100000번까지 주어질 수 있으므로 완전 탐색(O(N^2))으로는 시간초과가 난다.
• 이진 탐색을 통해 O(NlgN)으로 풀게되면 해결할 수 있다.
• 이진 탐색을 하기위해서는 정렬이 필수적인 선행조건이므로 정수 집합 A를 정렬한 후 이진탐색을 통해 속해있는지 찾으면 된다.
• 정렬은 O(NlgN)이고, 하나의 수가 집합 A에 속해있는지 이진탐색으로 찾는데는 O(lgN)이 걸리고, 그런 탐색을 N번 해야되므로 이 문제의 시간복잡도는 o(NlgN)이다.
• 정답률이 낮아 다른 뭔가가 있는지 겁 먹었었는데 이 문제는 O(NlgN)알고리즘이면 2초안에 해결할 수 있다는 확신을 갖고 바로 풀면 된다.

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

int bs(vector <int>& v, int num, int left, int right) {
	int mid = (left + right) / 2;
	if (right == left) {
		if (v[left] == num) return 1;
		else return 0;
	}
	else {
		if (v[mid] == num) return 1;
		else if (v[mid] < num) return bs(v, num, mid + 1, right);
		else return bs(v, num, left, mid);
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	cin >> N;
	vector <int> v;
	for (int n = 0; n < N; n++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	sort(v.begin(), v.end());
	int M;
	cin >> M;
	for (int m = 0; m < M; m++) {
		int n;
		cin >> n;
		int ans = bs(v, n, 0, N - 1);
		cout << ans << "\n";
	}
	return 0;
}