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

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

 

각 집합 A,B에 대한 입력을 받고 A-B와 B-A의 합집합을 구하면 된다. 나는 set 자료형을 사용하여 두 집합을 입력받은 뒤 각 집합을 순회하면서 find함수를 통해 해당원소가 다른 집합의 원소가 아니라면 정답 set자료형에 넣어주고 마지막으로 그 자료형의 크기를 출력해주었다. 

하지만 STL의 set_difference 알고리즘을 사용하는 것이 각 집합간의 차집합을 구하는데 효율적일 수 있다.

set_difference는 정렬된 범위에서 한 집합에서 다른 집합에 없는 요소를 추출한다.

 

set_difference 함수는 각 집합의 시작과 끝, 결과값을 저장할 변수를 매개변수로 사용한다.

 

set_difference 

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,
                         OutputIt d_first );

 

정답코드1(순회)

#include "iostream"
#include "set"

using namespace std;

set<int> s1, s2, answer;
int main()
{
	int n, m;

	cin >> n >> m;

	//집합만들기
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		s1.insert(x);
	}

	for (int i = 0; i < m; i++)
	{
		int x;
		cin >> x;
		s2.insert(x);
	}

	int cnt = 0;

	for (auto it = s1.begin(); it != s1.end(); it++)
	{
		if (s2.find(*it) == s2.end()) cnt++;
	}

	for (auto it = s2.begin(); it != s2.end(); it++)
	{
		if (s1.find(*it) == s1.end()) cnt++;
	}

	cout << cnt << endl;
}

 

 

정답코드2(STL알고리즘 활용)

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

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    set<int> s1, s2;  // 두 집합을 저장할 set

    // 집합 A 입력
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s1.insert(x);
    }

    // 집합 B 입력
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        s2.insert(x);
    }

    vector<int> diff1, diff2;  // 차집합을 저장할 벡터

    // A - B 차집합
    set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(diff1));

    // B - A 차집합
    set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(), back_inserter(diff2));

    // 대칭 차집합의 원소 개수
    cout << diff1.size() + diff2.size() << endl;

    return 0;
}