[백준/C & C++] 10815 숫자 카드

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

10815번: 숫자 카드

C

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

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 > num2) return 1;
	else if (num1 < num2) return -1;
	else return 0;
}

int binarySearch(int start, int end, int find, int arr[])
{
	int mid;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (find == arr[mid]) return 1;
		else if (find < arr[mid]) end = mid - 1;
		else if (find > arr[mid]) start = mid + 1;
	}
	return 0;
}

int main()
{
	int a, b;
	scanf("%d", &a);
	int* arrA = (int*)malloc(sizeof(int) * a);
	for (int i = 0; i < a; i++) scanf("%d", &arrA[i]);

	scanf("%d", &b);
	int* arrB = (int*)malloc(sizeof(int) * b);
	for (int i = 0; i < b; i++) scanf("%d", &arrB[i]);
	
	qsort(arrA, a, sizeof(int), compare);

	for (int i = 0; i < b; i++) printf("%d ", binarySearch(0, a - 1, arrB[i], arrA));
	return 0;
}

C++

#include <iostream>
#include <cstdlib>
using namespace std;

int compare(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 > num2) return 1;
	else if (num1 < num2) return -1;
	else return 0;
}

int binarySearch(int start, int end, int find, int arr[])
{
	int mid;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (find == arr[mid]) return 1;
		else if (find < arr[mid]) end = mid - 1;
		else if (find > arr[mid]) start = mid + 1;
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int a, b;
	cin >> a;
	int* arrA = new int[a];
	for (int i = 0; i < a; i++) cin >> arrA[i];

	cin >> b;
	int* arrB = new int[b];
	for (int i = 0; i < b; i++) cin >> arrB[i];

	qsort(arrA, a, sizeof(int), compare);

	for (int i = 0; i < b; i++) cout << binarySearch(0, a - 1, arrB[i], arrA) << " ";

	delete[]arrA;
	delete[]arrB;
	return 0;
}

코드 설명

상근이가 가진 숫자 카드의 개수 a를 입력받고,  숫자카드에 적힌 정수를 저장하는 동적배열을 만든 후 값을 반복문을 통해 입력받는다. 상근이가 가지고 있는지 확인해야 할 수의 개수 b를 입력받고, 정수를 저장하는 동적배열을 만든 후 값을 반복문을 통해 입력받는다. 

 

각각의 배열을 qsort를 이용해서 오름차순으로 정렬한다. 반복문을 b만큼 반복하면서 이진탐색으로 값이 있는지 찾고 있다면 1을, 없으면 0을 출력한다. 

 

동적배열들을 해제하고 프로그램을 종료한다. 

 

느낀 점

이진탐색을 이용하면 빠르게 풀 수 있는 문제다. 아무 생각없이 이진탐색을 사용하지 않고 문제를 풀었다가 시간 초과가 나와서 바로 이진탐색을 사용하니 통과했다.