백준(C언어)/23년 7월
[C] 백준 - 1920번: 수 찾기
C0MPAS
2023. 7. 4. 19:40
7월 4일(화) - 자료 구조 (1920번)
1920번: 수 찾기
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들
www.acmicpc.net
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
최초 생각 정리
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
문제점
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
풀이
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>
#include <stdlib.h>
int A[100000];
int B[100000];
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 binary_search(int left, int right, int key, int* arr)
{
while (left <= right)
{
int 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(void)
{
int N, M;
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
scanf("%d", &A[i]);
}
scanf("%d", &M);
for (int i = 0; i < M; i++)
{
scanf("%d", &B[i]);
}
qsort(A, N, sizeof(int), compare);
for (int i = 0; i < M; i++)
{
printf("%d\n", binary_search(0, N - 1, B[i], A));
}
return 0;
}ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ