[백준BaekJoon]1920: 수 찾기C++

문제

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

 

풀이

소요 시간: 10 ~ 15분

 

하나 하나씩 비교할 경우 N * M 의 시간복잡도가 발생하기 때문에, 이분 탐색을 통하여 시간을 줄이면 된다. 

주의할 점으로는

 

1. 탐색을 진행할 배열에 대해서는 오름차순 정렬을 해주어야 한다. 

2. 이 문제의 경우 그래도 시간 초과가 발생하여서...... 조금 당황했다. 

출력을 할 때 endl 을 사용하지 않고 개행문자를 적어줘서 문제를 해결했다. 

 

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

int arr[MAX];
int N, M;

void BinarySearch(int num) {
	int st = 0, en = N - 1;

	while (st <= en) {
		int mid = (st + en) / 2;

		if (arr[mid] == num) {
			cout << 1 << '\n';
			return ;
		}
		else if (arr[mid] < num) {
			st = mid + 1;
		}
		else {
			en= mid - 1;
		}
	}
	cout << 0 << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	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++) {
		int x;
		cin >> x;

		BinarySearch(x);
	}
}