집합과 맵 - 10815번

1월 17일(화) - 집합과 맵(10815번)

10815번: 숫자 카드

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- n개의 card_list 숫자들은 퀵정렬을 이용해서 오름차순으로 정렬해놓는다(정렬 -> https://jh4995.tistory.com/77)

- m개의 number_list 는 m개의 숫자 하나하나를 key 값으로 설정한 뒤, n개의 오름차순정렬된 card_list와 이진탐색을 진행한다

(이진탐색 -> https://jh4995.tistory.com/84)

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 이진탐색의 개념만 알고있을뿐 실제로 프로그램을 돌려본 적이 거의 없었고, 전달받아야할 매개변수도 변경해야했다

-> 자료구조에 정리해놓은 이진탐색 코드에서 low와 high 값을 매개변수가 아닌 함수내로 넣으면서 값을 각각 0 과 n으로 설정

-> 매개변수에 card_list[] 와 n을 추가하고, key 값은 매번 변화하는 number_list[0~m-1] 로 설정

-> m개의 number_list 에 들어있는 숫자가 n개의 card_list 에 중복으로 존재하면 1을 , 존재하지 않으면 -1을 return하도록 변경

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

int compare(const void* a, const void* b)
{
	if (*(int*)a > *(int*)b)
	{
		return 1;
	}
	else if (*(int*)a < *(int*)b)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int search_binary(int card_list[], int n, int key)
{
	int middle;
	int low = 0;
	int high = n;

	while (low <= high)
	{
		middle = (low + high) / 2;
		if (key == card_list[middle])
		{
			return 1;
		}
		else if (key > card_list[middle])
		{
			low = middle + 1;
		}
		else
		{
			high = middle - 1;
		}
	}
	return -1;
}

int main(void)
{
	int i;
	int exist = 0;

	int n;
	scanf("%d", &n);
	int* card_list = (int*)malloc(sizeof(int) * n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &card_list[i]);
	}
	
	int m;
	scanf("%d", &m);
	int* number_list = (int*)malloc(sizeof(int) * m);
	for (i = 0; i < m; i++)
	{
		scanf("%d", &number_list[i]);
	}
	
	qsort(card_list, n, sizeof(int), compare);

	for (int i = 0; i < m; i++)
	{
		exist = search_binary(card_list, n, number_list[i]);

		if (exist == 1)
		{
			printf("%d ", 1);
		}
		else
		{
			printf("%d ", 0);
		}
	}

	free(card_list);
	free(number_list);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ