[백준] 1920 수 찾기

수 찾기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

 

1 초

128 MB

249191

76985

51061

29.991%

문제

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

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1 복사

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

1
1
0
0
1

 

시간 제한이 1초인 문제이므로, A배열에서 수를 찾을때, 정렬 후 이진 탐색으로 찾아야 한다.

 

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

int previous_compare_int(const void* a, const void* b){
	return (*(int*)a-*(int*)b)
}

int compare_int(const void* a, const void* b) {
	int int_a = *(const int*)a;
	int int_b = *(const int*)b;

	if (int_a < int_b) return -1; 
	if (int_a > int_b) return 1;  
	return 0; 
}

//only if array1, array2 's size is same, and array1 is sorted
void check_and_print(int* array1, int* array2, int num_array1, int num_array2) {
	char flag = 0; //default is 0
	int left, right, middle, search_value;
	
	for (int i = 0; i < num_array2; i++) { //find array2's member in array1
		left = 0;
		right = num_array1 - 1;
		search_value = array2[i];

		//b-search
		while (left <= right) {
			middle = left + (right - left) / 2;
			if (array1[middle] > search_value) {
				right = middle - 1;
			}
			else if (array1[middle] < search_value) {
				left = middle + 1;
			}
			else if (array1[middle] == search_value){
				flag = 1;
				break;
			}
		}

		//here to print
		if (flag) {
			printf("1\n");
			flag = 0;
		}
		else {
			printf("0\n");
		}
	}
 }

int main() {
	int num_array1 = 0;
	int num_array2 = 0;
	int* array1 = NULL;
	int* array2 = NULL;


	scanf("%d", &num_array1);
	array1 = (int*)malloc(sizeof(int) * num_array1);
	for (int i = 0; i < num_array1; i++) {
		scanf("%d", &array1[i]);
	}

	scanf("%d", &num_array2);
	array2 = (int*)malloc(sizeof(int) * num_array2);
	for (int i = 0; i < num_array2; i++) {
		scanf("%d", &array2[i]);
	}
	
	qsort(array1, num_array1, sizeof(int), compare_int);
	

	check_and_print(array1, array2, num_array1, num_array2);
	
	free(array1);
	free(array2);

	return 0;
}

 

"previous_compare_int"는 초반에 작성한 함수로, 첫번째 인자가 큰 경우 양수, 같을경우 0, 두번째 인자가 클 경우 음수를 반환하게 설계하였지만, 입력의 최댓값이 2^31이므로 차를 구하는 과정에서 첫 인자가 2^31 - 1, 두번째 인자가 -1 이하긴 경우에 integer_overflow가 발생하므로 의도한대로 함수가 작동하지 않는다.

따라서, 대소 비교 후 +1, 0, -1을 반환하는 함수로 변경하였다.