백준 1269번 - 대칭 차집합

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

1269번: 대칭 차집합

사고과정)

1. (A집합 갯수 - 교집합 갯수 ) + (B집합 갯수 - 교집합 갯수) 하면 되겠구나. 그러면 교집합을 만들어야하네.

2. A와 B를 서로 비교해가면서 같은 걸 교집합 배열에 넣어야겠다.

- > 여기서 문제 봉착. 원소의 갯수가 너무 크고(각 200,000)이다 보니 이중 반복문으로 일일이 반복하면 시간복잡도(n^2)이라 너무 시간이 오래 걸려서 시간 초과가 뜸.

3. 그렇다면 어쩌지 하다가 입력받는 배열들의 원소가 정렬이 안되어있다면 최악의 경우로 모든 배열 원소들을 다 둘러보게 된다는 걸 깨닫. 그러면 우선 정렬을 해야겠다.

4. 각 A와 B 집합의 원소들을 오름차순으로 정렬.

5. 정렬 후 반복문 갯수를 줄이기 위해, 

int i = 0, j = 0;

while(i < A갯수 && j < B 갯수)를 이용해 먼저 작은 배열 도달하면 끝나게 만듦.

6. 생각해보니 그냥 교집합의 갯수만 필요하니, 굳이 교집합의 배열을 구현하지 않고, 그냥 int num = 0; 교집합 원소가 생길 때마다 num++해주면 됨.

7. 만약 비교했는데 같지 않다면 ? 작은 값을 다음 배열 인덱스로 옮겨가서 비교해야겠지.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int a, b = 0;	// A와 B의 원소 갯수 
	cin >> a >> b;


	int* A = new int[a];
	int* B = new int[b];

	for (int i = 0; i < a; i++)
		cin >> A[i];
	for (int i = 0; i < b; i++)
		cin >> B[i];

	sort(A, A + a);
	sort(B, B + b);

	int i = 0, j = 0;
	int num = 0;
	while (i < a && j < b)
	{
		if (A[i] == B[j])
		{
			num++;
			i++, j++;
		}
		else
		{
			A[i] > B[j] ? j++ : i++;
		}
	}
	

	int number = (a - num) + (b - num);

	cout << number;

	return 0;
}