백준 1920번

수 찾기

시간 제한 : 1초 메모리 제한 : 128 MB

문제

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 없으면 0을 출력하는 간단한 문제이다. 첫번째 배열에서 같은 값을 빠르게 찾으려면 이진탐색법으로 간단하게 풀수있다. 첫번째 배열을 qsort로 정렬 후 이진탐색법을 이용해서 있으면 1 없으면 0을 출력하게 하면 된다.

#define _CRT_SECURE_NO_WARNINGS    
#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;
	}
	if (num1 > num2)
	{
		return 1;
	}
	return 0;
}


int bray(int data[], int a, int high) {
    int low = 0;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (data[mid] == a)
        {
            return 1;
        }
        else if (data[mid] > a)
        {
            high = mid - 1;
        }
        else if (data[mid] < a)
        {
            low = mid + 1;
        }
    }
    return 0;
}

int main(void) {
	int n;
	scanf("%d", &n);
	int arr[n];

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	int m;
	scanf("%d", &m);
	int arr2[m];

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

	qsort(arr, n, sizeof(int), compare);

	for (int j = 0; j < m; j++) {
		printf("%d\n", bray(arr, arr2[j], n-1));
	}
	return 0;
}

Written on September 25, 2022