[C언어] 백준 1920번 수 찾기

링크

https://www.acmicpc.net/problem/1920

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;
}

 

 

 

 

 

 

제출 결과

---