백준 : 1920번, 수 찾기

문제 주소 : www.acmicpc.net/problem/1920

정답 비율 : 30.409% (2021.04.29 23:30 기준)

1920번: 수 찾기

 

문제 조건 :

입력 : N개의 데이터와 M개의 데이터가 주어집니다. (M, N : 1 ~ 100000, 데이터 : int 범위 안)

출력 : M의 n번째 데이터가 N의 데이터에 있으면 1 출력 아닌 경우에는 0 출력

시간 : 2초

 

문제 풀이 :

이 역시 간단한 문제입니다. 정렬과 이진 탐색을 알고 있는지 묻는 문제입니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int arr[100000];
int find[100000];

void quick_sort(int arr[], int s, int e);

int binary_search(int arr[], int data, int s, int e);


int main(void) {
	int Aindex, Sindex;

	scanf("%d", &Aindex);

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

	scanf("%d", &Sindex);

	for (int i = 0; i < Sindex; i++)
		scanf("%d", &find[i]);
	
	quick_sort(arr, 0, Aindex - 1);

	for (int i = 0; i < Sindex; i++) {
		printf("%d\n", binary_search(arr, find[i], 0, Aindex));
	}
	return 0;
}

void quick_sort(int arr[], int s, int e) {
	int pivot = s;
	int left = s + 1, right = e, tmp;

	tmp = arr[(s + e) / 2];
	arr[(s + e) / 2] = arr[s];
	arr[s] = tmp;

	while (left <= right) {
		while (left <= e && arr[pivot] >= arr[left])
			left++;

		while (s < right && arr[pivot] <= arr[right])
			right--;

		tmp = arr[right];
		if (left > right) {
			arr[right] = arr[pivot];
			arr[pivot] = tmp;
			pivot = right;
		}
		else {
			arr[right] = arr[left];
			arr[left] = tmp;
		}
	}

	if (pivot - s > 0)
		quick_sort(arr, s, pivot - 1);
	if (e - pivot > 0)
		quick_sort(arr, pivot + 1, e);

}

int binary_search(int arr[], int data, int s, int e) {
	int mid = (s + e) / 2;

	if (s <= e) {
		if (arr[mid] == data)
			return 1;
		else if (arr[mid] > data) {
			return binary_search(arr, data, s, mid - 1);
		}
		else {
			return binary_search(arr, data, mid + 1, e);
		}
	}
	else {
		return 0;
	}
}

 

 

 

***

다른 사람의 풀이를 보았는데 아주 신기한 기법을 사용한 풀이를 보았습니다. 아직 공부가 부족하여 해당 코드를 이해하지 못하였는데 나중에 이해하면 추가하겠습니다.

***