알고리즘

BOJ [1920] 수 찾기

감동이중요해 2017. 8. 14. 20:01

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;
}