백준 1920 : 수 찾기

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

1920번: 수 찾기

 

N이 최대 10만, M이 최대 10만이므로 N^2 풀이는 시간 초과가 발생한다. N개의 원소를 가진 배열을 받아 정렬 후 이분탐색으로 풀면된다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100'000];

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m, tmp; 
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	sort(arr, arr + n);

	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> tmp;
		cout << binary_search(arr, arr + n, tmp) << '\n';
	}
	return 0;
}

메모리: 2412 kb

시간: 60 ms