10815: 숫자 카드

자료구조

실버5

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

10815번: 숫자 카드

 

-결과

 

-코드

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

 

-풀이

이진탐색으로 풀어야 한다. 

단, 이런 이진탐색 문제는 먼저 정렬을 해야 한다.

따라서, 오름차순으로 카드를 정렬하고 하나씩 이진탐색을 해야 한다.

qsort 함수로 정렬을 시키고, 이진탐색으로 숫자 카드에 해당 카드를 찾으면 1을 출력하고 아닐 때는 0을 출력하도록 작성하면 된다.