[1269] 대칭 차집합

 

대칭 차집합 : (A-B) U (B-A)

 

처음에는 메모이제이션을 이용하여 배열을 크게 잡았더니 메모리 초과가 났다

#include <iostream>
using namespace std;

int N, M;
int A[100000001];
int B[100000001];
int larger1 = -1;
int larger2 = -1;
int cnt;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int input;
		cin >> input;
		A[input]++;
		if (input > larger1)larger1 = input;
	}
	for (int i = 0; i < M; i++) {
		int input;
		cin >> input;
		B[input]++;
		if (input > larger2)larger2 = input;
	}

	for (int i = 0; i <= larger1; i++)
	{
		if (A[i]) {
			if (!B[i])cnt++;
		}
	}
	for (int i = 0; i <= larger2; i++)
	{
		if (B[i]) {
			if (!A[i])cnt++;
		}
	}

	printf("%d", cnt);
}

 

그래서 결국 집합을 썼다..

집합 2개를 만들고 for문을 2번 돌린다

중복된 숫자가 없다면 count를 세주어 대칭 차집합의 개수를 증가시켜줬다

중복된 숫자를 찾는 코드는 find함수를 이용한다

if (myset2.find(*iter) != myset2.end()) // 중복된 숫자가 있다면

 

완성된 코드는 아래와 같다

#include <iostream>
#include <set>
using namespace std;

int N, M;
int cnt;
set<int> myset1;
set<int> myset2;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int input;
		cin >> input;
		myset1.insert(input);
	}

	for (int i = 0; i < M; i++) {
		int input;
		cin >> input;
		myset2.insert(input);
	}

	set<int> ::iterator iter;
	for (iter = myset1.begin(); iter != myset1.end(); iter++)
	{
		if (myset2.find(*iter) != myset2.end()) { // 중복된 숫자가 있다면

		}
		else {
			cnt++;
		}
	}
	for (iter = myset2.begin(); iter != myset2.end(); iter++)
	{
		if (myset1.find(*iter) != myset1.end()) { // 중복된 숫자가 있다면

		}
		else {
			cnt++;
		}
	}
	printf("%d", cnt);
}