[백준] BOJ 1920번 수 찾기

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

1920번: 수 찾기

 

문제 : 

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력 :

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

 

해결 :  
이진 탐색 문제이다.
이진 탐색 알고리즘이 어떤 것인지 간단히 정리하고 넘어가자면,
이진 탐색은 선형적인 탐색을 했을 때의 O(n^2)의 수행시간을 O(logN)의 시간으로 줄이는 획기적인 알고리즘이다.

간단히 설명하자면 정렬된 상태의 데이터의 중앙값과 탐색할 값과 비교하여 크다면 큰값부터 끝까지, 작다면 처음부터 mid보다 작은값까지로 범위를 반으로 축소하여 이를 반복한다.

 

값을 입력받을 때마다 이진탐색 알고리즘을 통해 값이 존재하는지 존재하지 않는지를 체크한다. 그리고 그 결과에 따른 값을 각각 출력한다.

/* 
iostream 대신 cstdio를 사용하여야한다. iosteam으로 인풋과 아웃풋을 구현하니 시간초과가 발생하였다.
++추가
ios::sync_with_stdio(false);
cin.tie(NULL);
메인 함수에 위 코드를 추가하면 iostream로 구현하여도 무방하다.
*/

#include <cstdio>
#include <algorithm>

using namespace std;

int N;
int M;
int A[100001];
int B;

bool findNumber(int num)
{
	int left = 0;
	int right = N - 1;

	if(A[left] > num || A[right] < num)
		return false;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		if(num < A[mid])
			right = mid - 1;
		else if(num > A[mid])
			left = mid + 1;
		else return true;
	}

	return false;
}

int main()
{
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
	{
		scanf("%d", &A[i]);
	}
	sort(A,A+N);

	scanf("%d", &M);
	for(int i = 0; i < M; i++)
	{
		scanf("%d", &B);
		if(findNumber(B))
			printf("1\n");
		else printf("0\n");
	}
	return 0;
}