백준 10815 숫자 카드 (자료구조 실버 5)

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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을 공백으로 구분해 출력한다.

내 제출

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

실버 난이도의 자료구조 문제 답게 이진 탐색을 사용하더라도 그냥 정렬하면 시간 초과가 난다.

그렇기 때문에 보다 효율적인 자료구조를 이용해 정렬을 해야 하는데, 나는 퀵 소트를 사용했다.

이진 탐색 함수를 정의해서 가운데를 기준으로 왼쪽/오른쪽으로 분기한다.

그리고 퀵 소트 함수를 이용해서 빠르게 정렬한다.

동적으로 메모리를 할당했기 때문에 마지막에 free까지 해준다.