[백준] 10815번: 숫자 카드 (C언어)

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

10815번: 숫자 카드

난이도: solved.ac 실버 5

 

이분 탐색을 활용하는 문제다

 

이분 탐색이란, 업다운 게임과 같은 방식으로 탐색을 하는 것이다

​

A가 1부터 50까지의 수 중에서 마음속으로 18이라는 수를 생각했고

​

B는 그 수를 맞춰야 하는 상황이라고 해보자

​

B: 음... 25?

A: DOWN (25보다 작으므로)

B: 12!

A: UP

(이제 B는 그 수가 12보다는 크고 25보다 작다는 것을 알게 된다)

B: 20

A: DOWN

B: 18

A: 정답!

​

이분 탐색은 이런 방식으로 탐색하는 알고리즘이다

​

나는 먼저 arr1라는 배열에 상근이가 가진 N개의 숫자를 저장하고

​

오름차순으로 정렬한 뒤

​

arr2라는 배열에 확인할 M개의 정수를 저장하여

​

하나씩 이분 탐색을 진행하였다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int compare(int* a, int* b) {
	return *a - *b;
}

int finding(int*, int, int, int);
int arr1[500001];
int arr2[500001];

int main() {
	int N, M;
	int i;
	scanf("%d", &N);

	for (i = 0; i < N; i++)
		scanf("%d", &arr1[i]);
	qsort(arr1, N, sizeof(int), compare);

	scanf("%d", &M);

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

	for (i = 0; i < M; i++)
		printf("%d ", finding(arr1, 0, N - 1, arr2[i]));
	return 0;
}

int finding(int* arr1, int left, int right, int num) {
	int middle = (left + right) / 2;
	if (num == arr1[middle])
		return 1;
	
	else if (num < arr1[middle]) {
		if (left == right)
			return 0;
		else
			finding(arr1, left, middle, num);
	}
	else {
		if (left == right)
			return 0;
		else
			finding(arr1, middle + 1, right, num);
	}
}