BOJ 1920 : 수 찾기

#BOJ 1920 : 수 찾기

1920번: 수 찾기

#풀이

N 과 M 이 100,000 개로 선형 탐색을 하여 찾기엔 시간초과가 생긴다.

 

그래서 정렬 한 뒤 이분 탐색으로 시간을 줄여 해결할 수 있다.

 

이분 탐색은 정렬되어 있는 순열에서

arr[idx] > num 이면 idx + 1 부터 end 까지의 인덱스에서 num을 발견할 수 있고

arr[idx] < num 이면 start 부터 idx -1 까지의 인덱스에서 num을 발견할 수 있다.

 

이렇게 반복하여 num을 순열에서 탐색하는 방법이다.

 

STL sort() 함수는 quick sort 를 활용하여 worst케이스에도 O(nlogn) 을 보장해준다.

이분 탐색(binary search)는 O(logn) 시간을 갖는다.

 

#코드

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int m;
int arr1[100002];
int arr2[100002];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr1[i];
	}
	sort(arr1 + 1, arr1 + n + 1);
	cin >> m;
	int start = 1;
	int End = m;
	for (int i = 1; i <= m; i++) {
		cin >> arr2[i];
		int start = 1;
		int End = n;
		int flag = 1;
		while(start <= End) {
			int idx = (start + End) / 2;
			if (arr1[idx] == arr2[i]) {
				cout << 1 << '\n';
				flag = 0;
				break;
			}
			else if (arr1[idx] > arr2[i]) {
				End = idx - 1;
			}
			else {
				start = idx + 1;
			}

		}
		if (flag)
			cout << 0 << '\n';
	}
	
	return 0;
}