집합과 맵 - 1269번

1월 27일(금) - 집합과 맵 (1269번)

1269번: 대칭 차집합

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

 

최초 생각 정리

- 집합과 맵 주제의 풀이들과 유사하게, 풀이 진행을 계획

(입력 -> 퀵정렬 -> 이진탐색 -> 중복 숫자 개수 파악 -> 중복 숫자의 2배를 전체개수에서 빼며 출력)

- A의 원소의 개수 n개는 a_number 에 입력받은 이후에 qsort

(이후 이진탐색을 위해서)

- B의 원소의 개수 m개는 b_number 에 입력받음

- 이진탐색을 통해서 key 값으로 설정한 B의 원소 1개와 A의 원소와 겹치면 +1을, 겹치지 않으면 0을 return

- 이진탐색결과로 return 받은 값들은 overlap 변수에 모두 더하며, 집합 A와 집합 B에서 겹치는 원소의 개수를 카운팅

- 마지막 대칭차집합의 원소의 개수로는  (A의 원소의 개수 n개) + (B의 원소의 개수 m개) - (overlap * 2) 를 출력

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

 

문제점

x

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

 

풀이

#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 number_list[], int size, int key)
{
	int middle;
	int low = 0;
	int high = size-1;

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

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	int* a_number = (int*)malloc(sizeof(int) * n);
	int* b_number = (int*)malloc(sizeof(int) * m);

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

	int overlap = 0;
	for (int j = 0; j < m; j++)
	{
		scanf("%d", &b_number[j]);
		overlap = overlap + search_binary(a_number, n, b_number[j]);
	}

	overlap = overlap * 2;
	printf("%d", n + m - overlap);

	return 0;
}

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