[백준 1822] 차집합(병합정렬,set사용)

2019. 12. 7. 12:56

문제출처: https://www.acmicpc.net/problem/1822

문제

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1≤n(A), n(B)≤500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

풀이

대칭차집합문제 https://jow1025.tistory.com/21와 거의 유사한 문제입니다. 병합정렬과 set을 이용한 2가지방법으로 풀어보았습니다.

병합정렬을 이용한 코드의설명은 대칭차집합문제와 거의 유사하기 때문에 생략하겠고 set방식또한 사용법만알면 풀 수 있는 문제입니다.

문제에서, a에있지만 b에는 없는원소는 a-b차집합을 구하면되는데, 값의 존재유무를 파악 할 때 set을 사용하기좋습니다.

단순히 set에 a원소를 다 넣고 b는 삽입하려는 원소가 a의 원소일 때 그 원소를 삭제합니다. 최종적으로 set에남은 원소는 a-b의 원소입니다.

c++의 set과 map은 메모리사용량이 높은 자료구조입니다. 이 문제에서 병합정렬 때 150만개의 배열을 선언해도 고작 한개의 set을 사용했을 때 2배넘는 메모리사용량을 보입니다.

코드

//#include<iostream>
//#include<set>
//using namespace std;
//int main()
//{
//	int a, b;
//	cin >> a >> b;
//	set<int>s;
//	set<int>::iterator it;
//	int x;
//	for (int i = 0; i < a; i++)
//	{
//		cin >> x;
//		s.insert(x);
//	}
//	for (int i = 0; i < b; i++)
//	{
//		cin >> x;
//		it = s.find(x);
//		if (it == s.end())
//			continue;
//		else
//			s.erase(x);
//	}
//	cout << s.size() << endl;
//	for (it = s.begin(); it != s.end(); it++)
//		cout<< *it<<" ";
//	cout << endl;
//}

#include<iostream>
#include<vector>
using namespace std;
int a[500001], b[500001], sorted[500001];
void merge(int a[], int start, int end);
void merge_sort(int a[], int start, int middle, int end);
int main()
{
	int n,m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < m; i++)
		cin >> b[i];
	merge(a, 0, n - 1);
	merge(b, 0, m - 1);
	vector<int>v;
	int a_start = 0;
	int b_start = 0;
	while (a_start < n && b_start < m)
	{
		if (a[a_start] < b[b_start])
		{
			v.push_back(a[a_start]);
			a_start++;
		}
		else if (a[a_start] > b[b_start])
			b_start++;
		else
		{
			a_start++, b_start++;
		}
	}
	if (a_start < n)
	{
		for (int i = a_start; i < n; i++)
			v.push_back(a[i]);
	}
	cout << v.size() << endl;
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;

}
void merge(int a[], int start, int end)
{
	if (start < end)
	{
		int middle = (start + end) / 2;
		merge(a, start, middle);
		merge(a, middle + 1, end);
		merge_sort(a, start, middle, end);
	}
}
void merge_sort(int a[], int start, int middle, int end)
{
	int i = start;
	int j = middle + 1;
	int k = start;
	while (i <= middle && j <= end)
	{
		if (a[i] <= a[j])
			sorted[k++] = a[i++];
		else sorted[k++] = a[j++];
	}
	if (i > middle)
	{
		for (int l = j; l <= end; l++)
			sorted[k++] = a[l];
	}
	else
		for (int l = i; l <= middle; l++)
			sorted[k++] = a[l];
	for (int l = start; l <= end; l++)
		a[l] = sorted[l];
}

결과