[백준 / C언어] 1920번: 수 찾기

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

1920번: 수 찾기

난이도: solved.ac 실버 4

 

 

정렬과 이분 탐색(Binary Search)을 활용한 문제다

 

나는 A라는 배열에 M개의 수를 저장한 후 qsort를 돌려주었고

 

B라는 배열에 M개의 수를 저장한 후 Binary Search 함수를 이용해 값이 있으면 1, 값이 없으면 0을 리턴하도록 만들었다

 

 

만약 나처럼 compare 함수를 이렇게 썼다면 아래의 전체 코드에 있는 compare 함수처럼 바꿔야 한다

 

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

 

위처럼 하면 5%에서 오답 처리가 되는데

 

아래의 케이스처럼 input에 2^(-32)나 2^32 가 있을 때 문제가 된다

4 2147483647 -5 -8 -11 4 2147483647 -5 -8 -11

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int A[100000];
int B[100000];

int compare(const void* a, const void* b) {
	int x = *(int*)a;
	int y = *(int*)b;
	if (x < y) return -1;
	else if (x > y) return 1;
	else return 0;
}

int main() {
	int N, M, i;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &A[i]);
	qsort(A, N, sizeof(int), compare);
	scanf("%d", &M);
	for (i = 0; i < M; i++)
		scanf("%d", &B[i]);

	for (i = 0; i < M; i++)
		printf("%d\n", find(B[i], 0, N - 1));
	
	return 0;
}

int find(int num, int start, int end) {
	if (end < start)
		return 0;
	
	int middle = (start + end) / 2;
	if (num == A[middle])
		return 1;
	else if (num < A[middle])
		find(num, start, middle - 1);
	else
		find(num, middle + 1, end);
}