[백준][C언어] #10815 숫자 카드

안녕하세요, 코딩하는 소연입니다 !🥰

이번 글은 백준 10815번 숫자 카드 문제를 C언어로 푼 것에 대한 기록입니다.

 

사진을 클릭하면 문제를 볼 수 있어요 !

 

1. 문제

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

 

2. 소스 코드

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

int binary_search(const int a[], int n, int key)
{
	int start = 0;
	int end = n - 1;
	int mid;

	do {
		mid = (start + end) / 2;

		if (a[mid] == key)
			return 1;
		else if (a[mid] < key)
			start = mid + 1;
		else
			end = mid - 1;
	} while (start <= end);

	return 0;
}

int compare(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* arr1;
	int* arr2;

	scanf("%d", &n);

	arr1 = (int*)calloc(n, sizeof(int));

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

	scanf("%d", &m);

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

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

	qsort(arr1, n, sizeof(int), (int(*)(const void*, const void*))compare);

	for (i = 0; i < m; i++)
	{
		printf("%d ", binary_search(arr1, n, arr2[i]));
	}

	free(arr1);
	free(arr2);

	return 0;
}

 

 

 

3. 풀이

우선 우리는 상근이가 가지고 있는 숫자 카드의 개수와 각 카드에 적힌 수들을 저장해두어야 합니다.

따라서 scanf를 사용하여 사용자로부터 상근이가 가지고 있는 숫자 카드의 개수 n을 입력받은 후,

calloc을 이용하여 크기가 n이고 0으로 초기화 된 1차원 동적 배열 arr1을 만들어줍니다.

이후 반복문을 돌며 각 숫자 카드에 적힌 수들을 사용자로부터 입력받아 arr1 배열에 저장해주면 되겠죠?

 

다음으로 우리는 주어진 숫자 카드의 개수와 각 카드에 적힌 수들도 저장해두어야 합니다.

앞에서 한 방법과 동일하게 하면 되겠죠?

주어진 숫자 카드에 적힌 수들은 arr2에 저장해두겠습니다.

 

이제 우리는 주어진 숫자 카드에 적힌 수가 상근이가 가지고 있는 숫자 카드에도 있는지를 확인해야 합니다.

 

저는 처음에 단순하게 2중 for문을 사용하여 주어진 카드에 적힌 수와 상근이가 가지고 있는 숫자 카드에 적힌 수를 모두 비교했었습니다.

그러나 이렇게 하면 시간 초과가 뜨더라구요..😢

 

그래서 생각해낸 방법이 상근이가 가지고 있는 숫자 카드들을 우선 오름차순으로 정렬한 후,

이진 탐색을 하여 주어진 숫자 카드에 있는 수를 상근이가 가지고 있는지를 확인하기로 했습니다!

 

따라서 우선 qsort를 활용하여 arr1에 저장된 상근이가 가지고 있는 숫자 카드들을 오름 차순으로 정렬해줍니다.

그리고 for문을 돌며 주어진 숫자 카드에 적혀있는 수를 상근이가 가지고 있는지 binary_search 함수를 통해 확인하며

가지고 있다면 1을, 가지고 있지 않다면 0을 바로바로 출력하도록 하였습니다.

 

마지막으로 우리가 사용했던 메모리들을 다시 반환해주어야 되겠죠?

free를 통해 arr1과 arr2 배열을 만들기 위하여 사용했던 메모리들을 반환해줍니다.