무지개 달팽이

Q. 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력.

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력.

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

기본적인 이진 탐색 문제이다. 

그러므로 아래와 같은 방법으로 문제를 해결해주면 된다.

"숫자 카드를 정렬(오름차순) + 정수 하나씩 탐색"

처음에는 단순 선택 정렬을 선택했는데 시간 초과가 났다. 그래서 퀵 정렬(qsort 함수 이용)로 바꿨을 때 문제를 해결한 것을 보고, 알고리즘에서 단순히 문제를 해결하는 것보다 효율적으로 해결하는 것이 중요하다는 것을 깨달았다.

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

int bin_search(const int a[], int n, int key)
{
	int pl = 0;
	int pr = n - 1;
	int pc;

	do {
		pc = (pl + pr) / 2;
		
		if (a[pc] == key)
			return 1;
		else if (a[pc] < key)
			pl = pc + 1;
		else
			pr = pc - 1;
	} while(pl <= pr);

	return 0;
}

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

int main(void)
{
	int i;
	int n, m;
	int *num;
	int *card;

	scanf("%d", &n);
	
	num = (int*)calloc(n, sizeof(int));

	for (i = 0; i < n; i++)
		scanf("%d", &num[i]);
	
	scanf("%d", &m);

	card = (int*)calloc(m, sizeof(int));

	for (i = 0; i < m; i++)
		scanf("%d",&card[i]);

	qsort(num, n, sizeof(int), (int(*)(const void *, const void *))int_cmp);

	for (i = 0; i < m; i++)
	{
		printf("%d ", bin_search(num, n, card[i]));
	}

	free(num); free(card);

	return 0;
}