1920: 수 찾기

-Class2 : Silver5

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

1920번: 수 찾기

 

-결과

 

-코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int compare(const void* first, const void* second)
{
	int* a = (int*)first;
	int* b = (int*)second;

	if (*a < *b)
		return -1;
	else
		return 1;
	return 0;
}

int binary_search(int list[], int n, int key)
{
	int left, mid, right;
	left = 0, right = n - 1;

	while (left <= right)
	{
		mid = (left + right) / 2;
		if (list[mid] == key)
			return 0;
		else if (list[mid] < key)
			left = mid + 1;
		else
			right = mid - 1;
	}
	
	return 1;
}

int main()
{
	int n, m, i, data;
	int* list;

	scanf("%d", &n);

	list = (int*)malloc(n * sizeof(int));

	for (i = 0; i < n; i++)
	{
		scanf(" %d", &list[i]);
	}

	qsort(list, n, sizeof(list[0]), compare);

	scanf(" %d", &m);

	for (i = 0; i < m; i++)
	{
		scanf(" %d", &data);
		
		if (binary_search(list, n, data) == 0)
			printf("1\n");
		else
			printf("0\n");
	}

	return 0;
}

 

-풀이

이 문제는 3달 전에 혼자 공부할 때부터 풀었던 문제인데, 엄청 많이 틀렸었던 문제이다.

찾아본 결과 배열은 통한 이진탐색을 이용하여 푸는 문제라고 한다.

배열 두 개를 만들어서 for문으로 값을 찾아 푸는 문제이다.