1920번 수 찾기(C)

실버문제를 하나씩 해결해보자

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

1920번: 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

사전지식

브론즈 문제 풀 때 시간복잡도라는 것인지 뭔지 걸려서, 단순히 앞에서부터 순서대로 탐색을 하게 되면 시간이 초과되는 경험을 해 본 적 있다...이 문제도 역시 이진 탐색을 활용해서 문제를 풀어야 하나 보다.

 

자료구조도 아직 배웠는데 이진 탐색을 쓰려 하니...오랜만에 1학기 수업 ppt를 꺼낼 수 밖에 없었다.

그림만 쓰겠습니다 교수님

왼쪽 인덱스(left)와 오른쪽 인덱스(right), 중간 인덱스(middle)를 설정한다. middle=(left+right)/2 로 구하고,

ⓐ 구하고자 하는 값 < middle : right=middle-1

ⓑ 구하고자 하는 값 > middle : left=middle+1

ⓒ 구하고자 하는 값 = middle : middle이 답

 

 

해결과정

1. 이진탐색에는 전제가 하나 있었다. 바로 데이터 집합이 사전에 정렬돼있어야 한다는 것이다.

C++에서는 sort함수라고 있는가본데, C에는 그게 없기 때문에 대체재를 찾아다녔다.

퀵 정렬이 <stdlib>에 함수로 있다는 사실을 알았다.

그래서 코딩도장님 자료보고 퀵 정렬 함수를 사용했다.

https://dojang.io/mod/page/view.php?id=638 

C 언어 코딩 도장: 73.2 퀵 정렬 함수 사용하기

 

2. 그리고 이진 탐색에 계속 오류가 나서...하늘서랍님 코드가 비록 C++이지만 아이디어만 얻는 겸 해서 나는 C로 작성했다.

https://artiper.tistory.com/96?category=951644 

백준 1920번 수 찾기 [C/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 left, int right, int key, int *arr) {
	int middle;

	while (left <= right) {
		middle = (left + right) / 2;
		if (key < arr[middle]) right = middle - 1;
		else if (key > arr[middle]) left = middle + 1;
		else return 1;
	}
	return 0;
}

int main() {
	int n, m;
	int i;
	int A[100000], B[100000];
	int result = 0;

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

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

	qsort(A, n, sizeof(int), compare);
	for (i = 0; i < m; i++) {
		result = BinarySearch(0, n - 1, B[i], A);
		printf("%d\n", result);
	}

	return 0;
}

 

결과

실버 성공<< 기분이가 좋네요