C++ [대칭 차집합_백준] / #map #set #자료구조

Problem

---

대칭 차집합-백준

1269번: 대칭 차집합

 

문제는 매우 간단하다.

첫 줄에 두 개의 숫자가 주어진다. 각각 집합 A와 B의 원소의 개수를 의미한다.

두 번째 줄에는 A의 원소가 주어진다.

세 번째 줄에는 B의 원소가 주어진다.

이 때 결과로 A와 B가 서로 겹치지않은 원소들의 개수를 구하면 된다.

Solve

---

필자는 당연히 A의 원소들을 B의 원소들과 하나씩 비교하여 같은 원소가 있으면 개수를 세놓은 뒤에 A의 총 원소에서 같은 원소의 갯수를 뺐다. 반대로 B의 경우도 그렇게 구한 뒤 두 값을 더하여 결과로 출력하였다.

나의 풀이

#include <iostream>
#include <algorithm>

using namespace std;

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

	int a, b;
	cin >> a >> b;
	int* a_arr = new int[a];
	int* b_arr = new int[b];
	int a_num, b_num;

	for (int i = 0; i < a; i++)
	{
		cin >> a_num;
		a_arr[i] = a_num;
	}
	for (int i = 0; i < b; i++)
	{
		cin >> b_num;
		b_arr[i] = b_num;
	}
	sort(a_arr, a_arr + a);
	sort(b_arr, b_arr + b);

	int a_cnt = 0, b_cnt = 0;
	for (int i = 0; i < b; i++)
	{
		if (binary_search(a_arr, a_arr + a, b_arr[i]))
		{
			a_cnt++;
		}
	}
	for (int i = 0; i < a; i++)
	{
		if (binary_search(b_arr, b_arr + b, a_arr[i]))
		{
			b_cnt++;
		}
	}
	int ans=0;
	ans = a + b - a_cnt - b_cnt;
	cout << ans;
	return 0;
}

 

그러나 백준 사이트의 경우 문제 하단에 알고리즘 분류가 더보기로 숨겨져있다. 해당 더보기를 눌러서 문제 풀이에 적절한 알고리즘의 힌트를 얻을 수 있다.

풀이에 성공했지만 궁금해서 눌러보고 매우 놀랐다...

 

set과 map에 원소를 추가할 때 중복되는 원소가 있을 경우 원소가 추가되지않고 insert함수의 return 값으로 pair<iterator, bool>을 반환하는데 이 때 bool은 중복 여부를 나타낸다.

이러한 방법을 이용하면 매우 간단하게 풀이할 수 있다.

 

1. set 객체를 생성한다.

2. A의 원소를 set의 객체에 추가한다.

3. B의 원소를 set의 객체에 추가한다. 이때 A에 존재하는 원소와 같은 원소를 추가하게 되면 중복된 원소는 추가되지않고 이때 return되는 pair의 second가 false이면 cnt를 1증가시킨다.

4. (set 원소의 갯수 - cnt) 를 출력한다.

 

set 응용 풀이

#include <iostream>
#include <set>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	set<int> s;

	int a, b;
	cin >> a >> b;
	int num;
	int cnt = 0;
	for (int i = 0; i < a; i++)
	{
		cin >> num;
		s.insert(num);
	}
	for (int i = 0; i < b; i++)
	{
		cin >> num;
		if (s.insert(num).second == false)
		{
			cnt++;
		}
	}
	cout << s.size() - cnt;
	return 0;
}

 

근데 특이한 점은 set을 이용하면 메모리와 소요시간이 더 커진다는 것이다. 이것에 대해서는 더욱 깊은 공부와 연구가 필요할것같다...

위가 set응용 풀이 / 아래는 나의 기존 풀이

 

set 클래스를 정리한 글에서 intellisense를 보면 return값을 확인할 수 있다.

2023.03.27 - [C++/자료구조] - C++ [자료구조] / # set #STL

C++ [자료구조] / # set #STL