[백준] 1269 대칭 차집합 with C++

문제설명

---

입출력 예제

---

개념

　집합 A와 B가 주어졌을 때 (A - B) ∪ (B - A)의 값을 구하는 문제다. 자료구조 map을 이용해서 푸는 방법도 있지만, 필자는 조금 다르게 풀었다.

1. 두 집합의 원소를 벡터에 삽입
2. 교집합을 이진 탐색을 이용하여 정수형 변수에 삽입
3. 벡터의 크기에서 교집합의 원소의 차를 출력

 

---

풀이

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
	int N, M, n, count = 0;
	std::cin >> N >> M;

	std::vector<int> v(N + M);

　집합 A, B의 원소의 개수 N, M, 입력받을 숫자 n, 교집합의 수 count를 초기화해준다. 그리고 N + M의 크기를 가지는 벡터 v를 초기화해 준다.

 

	for (int i = 0; i < N; i++)
		std::cin >> v[i];

	std::sort(v.begin(), v.end());

　N개의 숫자를 벡터에 초기화하고, 이진 탐색을 위해 정렬해 준다.

 

	for (int i = 0; i < M; i++)
	{
		std::cin >> n;

		if (std::binary_search(v.begin(), v.end(), n))
			count++;
	}

	std::cout << v.size() - 2 * count;
}

　M개의 숫자를 입력받는데, 만약 기존의 벡터 v에서 찾을 수 있다면 교집합의 원소이므로 count의 개수를 늘려준다. 그리고 최종적으로 집합의 전체 크기에서 교집합의 원소의 두 배를 빼주면 해결할 수 있다.

총합본

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
	int N, M, n, count = 0;
	std::cin >> N >> M;

	std::vector<int> v(N + M);

	for (int i = 0; i < N; i++)
		std::cin >> v[i];

	std::sort(v.begin(), v.end());

	for (int i = 0; i < M; i++)
	{
		std::cin >> n;

		if (std::binary_search(v.begin(), v.end(), n))
			count++;
	}

	std::cout << v.size() - 2 * count;
}