[C] 1920번: 수 찾기
[C] 1920번: 수 찾기
문제
https://www.acmicpc.net/problem/1920
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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 보다 크거나 같고 보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
풀이
배열에서 어떤 수가 존재하는지 빠르게 확인하려면 먼저 정렬해야 합니다.
그다음 각 질의값마다 이분 탐색을 수행하면 됩니다.
- 배열을 정렬한다
- 찾고 싶은 값을 이분 탐색한다
- 찾으면
1, 없으면0출력한다
입력 크기가 크기 때문에, 단순 선형 탐색으로 매번 찾으면 시간이 오래 걸립니다.
정렬 후 이분 탐색을 사용하면 각 질의마다 빠르게 확인할 수 있습니다.
코드
#include <stdio.h>#include <stdlib.h>
int a[100000];
int compare(const void *x, const void *y) { int n1 = *(const int *)x; int n2 = *(const int *)y;
if (n1 < n2) return -1; if (n1 > n2) return 1; return 0;}
int binary_search(int key, int size) { int low = 0; int high = size - 1;
while (low <= high) { int mid = (low + high) / 2;
if (a[mid] == key) { return 1; } else if (key < a[mid]) { high = mid - 1; } else { low = mid + 1; } }
return 0;}
int main() { int n, m;
scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); }
qsort(a, n, sizeof(int), compare);
scanf("%d", &m); for (int i = 0; i < m; i++) { int x; scanf("%d", &x); printf("%d\n", binary_search(x, n)); }
return 0;}