링크
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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
예제 입력 1
5
4 1 5 2 3
5
1 3 7 9 5예제 출력 1
1
1
0
0
1아이디어 스케치
- 모든 정수의 범위는 -2^31 ~ 2^31 으로 signed int 형의 값의 범위를 만족하기 때문에 자료형은 int 형으로 설정한다.
- 대표적인 이분 탐색 알고리즘을 이용하는 문제로 이분 탐색은 값이 정렬되어 있는 상태에서만 사용할 수 있는 알고리즘이기 때문에 값을 먼저 오름차순으로 정렬을 해야한다.
코드 분할 설명
scanf("%d", &N);
arr1 = (int*)calloc(N, sizeof(int));
for (int i = 0; i < N; i++)
scanf("%d", &arr1[i]);
scanf("%d", &M);
arr2 = (int*)calloc(M, sizeof(int));
for (int i = 0; i < M; i++)
scanf("%d", &arr2[i]);
qsort(arr1, N, sizeof(arr1[0]), compare); //퀵 정렬- N과 값을 찾을 배열의 인자를 입력 받고, M과 찾을 요소의 배열의 인자를 입력 받은 후 퀵 정렬을 수행
int compare(const void* first, const void* second)
{
int a = *(const int*)first;
int b = *(const int*)second;
if (a < b)
return -1;
else if (a > b)
return 1; //오름차순 정렬
else
return 0;
}- 퀵 정렬 인자 중 비교함수를 구현한 것으로 현재 인덱스의 값이 바로 뒤의 인덱스의 값보다 크면 swap하여 오름차순으로 정렬한다.
int binary_search(int a[], int n, int key)
{
int start = 0;
int end = n - 1;
while (start <= end)
{
int mid = (start + end) / 2;
if (key > a[mid])
start = mid + 1;
else if (key < a[mid])
end = mid - 1;
else
return 1;
}
return 0;
}- 이 문제의 가장 핵심 알고리즘으로 이분 탐색 알고리즘이다.
- start와 end는 각각 탐색할 범위의 시작 지점과 종료 지점이다.
- 오름차순으로 정렬된 배열의 중간 값을 구한 후 찾으려는 값이 중간값보다 크면 중간값의 오른쪽에 위치하고, 작으면 왼쪽에 위치한다.
- 중간값보다 크면 오른쪽에 위치하므로 탐색지점의 시작점을 중간값의 인덱스+1을 해주고 다시 탐색한다.
- 중간값보다 작으면 중간값의 왼쪽에 위치하므로 탐색지점의 종료지점을 중간값의 인덱스-1로 해주고 다시 탐색을 진행한다.
- start지점이 end지점보다 커질 때 까지 값을 찾지 못하면 그 값은 배열에 존재하지 않는 값이므로 0을 return 해주고 함수를 종료하고, 찾은 경우에는 1을 return 해주고 함수를 종료한다.
for (int i = 0; i < M; i++) {
printf("%d\n", binary_search(arr1, N, arr2[i]));
}- return 값을 차례대로 출력한다.
- binary_search 함수의 인자로 찾을 배열, 배열의 크기, 찾을 요소를 설정해놨다.
전체코드
#include <stdio.h>
#include <stdlib.h>
int compare(const void* first, const void* second)
{
int a = *(const int*)first;
int b = *(const int*)second;
if (a < b)
return -1;
else if (a > b)
return 1; //오름차순 정렬
else
return 0;
}
int binary_search(int a[], int n, int key)
{
int start = 0;
int end = n - 1;
while (start <= end)
{
int mid = (start + end) / 2;
if (key > a[mid])
start = mid + 1;
else if (key < a[mid])
end = mid - 1;
else
return 1;
}
return 0;
}
int main()
{
int N, M;
int* arr1; // 탐색할 배열
int* arr2; // 찾을 요소를 담은 배열
scanf("%d", &N);
arr1 = (int*)calloc(N, sizeof(int));
for (int i = 0; i < N; i++)
scanf("%d", &arr1[i]);
scanf("%d", &M);
arr2 = (int*)calloc(M, sizeof(int));
for (int i = 0; i < M; i++)
scanf("%d", &arr2[i]);
qsort(arr1, N, sizeof(arr1[0]), compare); //퀵 정렬
for (int i = 0; i < M; i++) {
printf("%d\n", binary_search(arr1, N, arr2[i]));
}
free(arr1);
free(arr2);
return 0;
}제출 결과
IT Velog