BOJ [1920] 수 찾기

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

1. 분류

이분탐색

2. 풀이

먼저 N개의 숫자를 입력받은 뒤 이어서 입력받는 M개의 숫자가 먼저 받은 N개 숫자들 중 있는지를 찾는 문제.

N, M 둘다 최대 10만 개까지 입력이 가능하기 때문에 O(N^2) 이상은 무조건 시간 초과가 난다.

입력받은 숫자를 오름차순으로 정리한 뒤 이분탐색으로 찾는다면?

N개 입력 : O(N)

정렬 : sort 함수 이용 - O(NlogN)

탐색 : O(MlogN)

이 정도면 제한시간 내에 무리없이 찾아낼 수 있을 것이다.

3. 소스코드

#include <cstdio>
#include <algorithm>
int a[100000];

int main()
{
	freopen("input.txt", "r", stdin);
	int n, m;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);

	std::sort(a, a + n);

	for (scanf("%d", &m); m > 0; m--)
	{
		int b;
		scanf("%d", &b);

		int low = 0, high = n - 1, mid = 0, ans = 0;
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (b > a[mid])
				low = mid + 1;
			else if (b < a[mid])
				high = mid - 1;
			else
			{
				ans = 1;
				break;
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}