[Baekjoon] Class2 08 - 수 찾기 [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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

출력

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

생각해볼점

원래 배열을 퀵 정렬으로 정렬한 후, 이진 탐색을 이용해 찾는다.
처음엔 퀵 정렬을 직접 구현해서 썼었는데, 계속 시간 초과가 발생했다. 아무래도 피벗을 놓는 데서 퀵 정렬의 최악의 경우가 되는 것 같아 C에 내장되어있는 qsort함수를 사용했다.

코드 구현

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

static int compare(const void *a, const void *b)
{
	if (*(int *)a < *(int *)b)
		return (-1);
	else if (*(int *)a > *(int *)b)
		return (1);
	return (0);
}

static int binary_search(int *set_num_array, int set_num, int find_num)
{
	int	min = 0, max = set_num;
	int ans;

	while (min <= max)
	{
		ans = (min + max) / 2;
		if (find_num == set_num_array[ans])
			return (1);
		else if (find_num < set_num_array[ans])
			max = ans - 1;
		else
			min = ans + 1;
	}

	return (0);
}

int main()
{
	int	set_num, find_num;
	int	*set_num_array, *find_num_array;
	int	left, right, pivot, idx;

	scanf("%d", &set_num);
	set_num_array = (int *)malloc((set_num + 1)* sizeof(int));
	idx = 0;
	while (idx < set_num)
		scanf("%d", &set_num_array[idx++]);
	set_num_array[idx] = '\0';

	scanf("%d", &find_num);
	find_num_array = (int *)malloc((find_num + 1) * sizeof(int));
	idx = 0;
	while (idx < find_num)
		scanf("%d", &find_num_array[idx++]);
	find_num_array[idx] = '\0';

	qsort(set_num_array, set_num, sizeof(int), compare);

	idx = 0;
	while (idx < find_num)
		printf("%d\n", binary_search(set_num_array, set_num - 1, find_num_array[idx++]));
	
	free(set_num_array);
	free(find_num_array);
	return (0);
}