[C언어] 백준 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을 출력한다.

구상

N과 M이 최대로 주어질 경우 선형 탐색을 시행하면 $10^{12}$번을 확인해야 해서 시간이 정말 오래 걸린다.

이진 탐색(Binary Search)을 사용하면 시간을 훨씬 줄일 수 있다.

 

이진 탐색은 업앤다운 게임이다. 부르는 값보다 크면 업, 작으면 다운. 그렇게 경우를 줄여나면서 탐색한다.

이진 탐색을 하려면 수가 순서대로 정렬되어 있어야 하는데, 문제에서는 마구잡이로 수가 입력되므로 이를 정렬해줘야 한다. 정렬은 qsort 함수를 이용했다.

 

비교적 쉬운 개념을 적용할 때 실수하기 쉽다. end값은 입력받은 배열의 크기 n보다 1 작은 값에서 시작해야 정상적으로 배열에 접근하는데, 그냥 무턱대고 이진탐색 기본 코드를 따라하다가 end에 n을 대입해서 자꾸 오답이 나왔다. 

아무리 쉬운 코드라도 신중하게 작성해야 한다.

 

코드

#include <stdio.h>
#include <stdlib.h>

int compare(const void* arg1, const void* arg2) {
	int a = *(int*)arg1;    //void를 int형으로 변환
	int b = *(int*)arg2;
	//오름차순 정렬
	if (a > b) return 1;
	else if (a < b) return -1;
	else return 0;
}

int main(void)
{
	int n, m;	//수의 개수
	int first, end, mid;	//이진 탐색을 위한 변수
	int flag;	//결과 플래그

	scanf("%d", &n);
	int* arr1 = (int*)malloc(sizeof(int) * n);	//기준 배열
	for (int i = 0; i < n; i++)
		scanf("%d", &arr1[i]);

	scanf("%d", &m);
	int* arr2 = (int*)malloc(sizeof(int) * m);	//비교 배열
	for (int i = 0; i < m; i++)
		scanf("%d", &arr2[i]);

	qsort(arr1, n, sizeof(int), compare);	//이진 탐색을 위한 정렬

	for (int i = 0; i < m; i++) {
		first = 0, end = n - 1, flag = 0;
		while (first <= end) {	//탐색이 끝날 때까지
			mid = (first + end) / 2;	//중앙값

			if (arr2[i] == arr1[mid]) {	//값을 찾으면 종료
				flag = 1;
				break;
			}
			else if (arr2[i] < arr1[mid])	//중앙값보다 작을 때
				end = mid - 1;	//범위 좁히기
			else if (arr2[i] > arr1[mid])	//중앙값보다 클 때
				first = mid + 1;	//범위 좁히기
		}
		if (flag) printf("1\n");
		else printf("0\n");
	}

	free(arr1);	//할당 해제
	free(arr2);
	
	return 0;
}