(백준 1269번 대칭 차집합 C++) 라이님 블로그 대회 알고리즘 따라잡기 11) BST

Tree로 멘탈이 바사삭해서 잠시 휴식을 찾아 이 문제도 왔다..@_@

 

BST(Binary Search Tree)에 대한 설명은 아래 라이님 블로그를 따라가면 됩니다..🌟

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220789373847&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

이진 검색 트리(Binary Search Tree)

그 전에 알아두면 좋을 C++로 합집합, 차집합 구현하는 방법을 소개하고자 한다.

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220404011875

[C++ 강좌] 103 - 알고리즘 헤더 파일 (12) - merge(), set_union(), set_intersection(), set_difference(), set_symmetric_d

<algorithm> 헤더에 있는 함수 

1. merge()

merge(a, a+5, b, b+5, result.begin())을 하면 a와 b가 합쳐져서 result에 적힌다.

a: 1 4 5 5 8

b: 2 3 4 7 9

결과: 1 2 3 4 4 5 5 7 8 9

 

▣ 정렬, 중복 값 없는 리스크 준비

2. set_union()과 merge()와의 차이점 : 중복원소의 유무

결과의 끝 주소 또는 이터레이터를 return함

합집합 : set_union()

교집합 : set_intersection()

차집합 : set_difference()

대칭차집합 : set_symmetric_difference()

 

하지만,,! 아래와 같이 단순한 풀이도 가능하다!

백준 1269번

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

 

 

#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
constexpr int MAX_N = 100000000 + 1;

int main() {
	vector<bool> array;
	array.resize(MAX_N, false);
	
	int nA, nB; cin >> nA >> nB;
	int temp;
	for (int i = 0; i < nA; i++) {
		cin >> temp;
		array[temp] = 1;
	}

	for (int i = 0; i < nB; i++) {
		cin >> temp;
		if (array[temp] == 1) array[temp] = 0;
		else array[temp] = 1;
	}

	cout << accumulate(begin(array), end(array), 0, plus<float>()) << endl;
}

 

추가로 might_2님의 풀이가 좋아보여서 참고해보았다.

(내가 알아보기 쉽게 살짝의 수정을 가미하였음!!)

#include <iostream>
#include <set>

main() { 
	int a, b, n, c, d = 0; 
	std::cin >> a >> b; 
	std::set<int> A; 
	for (c = a + b; c--; A.insert(n)) { 
		std::cin >> n; 
		d += (c <= b && A.count(n)>0); 
	}
	std::cout << a + b - 2 * d; 
}