백준 1920 [C++]

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

1920번: 수 찾기

1. 풀이방법

- N개의 수중에 주어지는 M개의 수들이 각각 존재하는 지 확인해야합니다

 

- 선형탐색을 진행할 경우 O(N*M) 이므로 약 10,000,000,000 는 시간초과에 걸릴 것 같습니다.

 

- O(NlogN) 정렬 + O(M*logN) 이분탐색 으로 해결했습니다.

 

 

 

2. 주의사항

- 조건으로 인한 시간초과

 

 

3. 나의코드

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

int Narr[100000];
int N, M;
bool existnum(int target) {
	int ep = N - 1;
	int sp = 0;
	int mid;
	while (sp<=ep) {
		mid = (sp + ep) / 2;
		if (Narr[mid] == target) { return true; }
		else if (Narr[mid] < target) {
			sp = mid + 1;
		}
		else if (Narr[mid] > target) {
			ep = mid - 1;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Narr[i];
	}
	sort(Narr, Narr+N); //이분탐색을 위한 정렬
	cin >> M;
	int target;
	for (int i = 0; i < M; i++) {
		cin >> target;
		cout << existnum(target)<<"\n";
	}
	return 0;
}