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

1. 문제이해

1269번: 대칭 차집합 (acmicpc.net)

1269번: 대칭 차집합

 

집합 A와 B에서, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.

집합 A와 B가 주어질 때, 대칭 차집합의 원소의 개수를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

예전에 풀었던 차집합 문제와 거의 유사한 문제이다.

차집합 문제는 단순히 A - B의 차집합만 구해줘도 됐었다면,

이번 문제는 차집합 A - B, B - A 를 모두 구하고, 해당 차집합들의 합집합까지 구해야 한다.

이전에 풀었던 차집합 포스팅을 아래 포스팅을 참고하자.

 

https://beginnerdeveloper-lit.tistory.com/26

[C++] 백준 1822번 차집합

 

차집합을 구하는 과정은 위 포스팅의 차집합 풀이 과정과 동일하다.

 

set을 이용해주어

1. A - B 의 경우, 두 집합의 원소를 비교해, A에만 있는 원소를 남겨주고

2. B - A 의 경우, 두 집합의 원소를 비교해, B에만 있는 원소를 남겨주고

3. 두 집합을 합하여 원소의 개수를 세주었다.

 

다만, 여기서 한가지 주의할 점이 있다.

A - B의 연산을 할 경우, A의 원소 중 B와 겹치는 원소들은 삭제하는 연산을 수행하게 된다.

이렇게 되면, 집합 A가 자연스럽게 A - B 로 변환된다.

이후, B - A의 연산을 할 때, B의 원소 중 A와 겹치는 원소들을 삭제할 때,

이미 A는 A - B로 변환이 되어있으므로, B - A의 결괏값이 다르게 나오게 된다.

따라서, A와 동일한 집합을 하나 더 두어, 해당 집합과 B를 비교하여 B - A의 값을 구해야 한다.

 

위와 같은 점에 유의하여 완성된 코드는 다음과 같다.

 

 

 

3. 소스코드

#include <iostream>
#include <set>
using namespace std;

int main() {
	int a, b;          // 집합 A와 B의 원소의 개수
	int elementA;      // 집합 A의 원소를 입력, 저장하기 위한 변수
	int elementB;      // 집합 B의 원소를 입력, 저장하기 위한 변수
	set<int> A;        // 집합 A
	set<int> B;        // 집합 B
	set<int> tmpA;     // 집합 A의 복사본
	set<int>::iterator check;   // 원소의 유무를 구별하기 위한 변수
	set<int>::iterator t;       // for문 반복을 위한 변수

	cin >> a >> b;
	for (int i = 0; i < a; i++) {
		cin >> elementA;
		A.insert(elementA);
		tmpA.insert(elementA);
	}
	for (int i = 0; i < b; i++) {
		cin >> elementB;
		B.insert(elementB);
	}

	/* 1. A - B
	   (아래 연산을 통해 집합 A가 A-B로 변환) */
	for (t = B.begin(); t != B.end(); t++) {
		check = A.find(*t);     
		if (check == A.end()) {
			continue;
		}
		else {           
			A.erase(check);    
		}
	}

	/* 2. B - A
	   (1의 A - B 연산을 통해 A가 A - B 형태로 바뀌었으므로,
	    A의 복사본인 tmpA를 통해 B와 연산하여, B를 B - A로 변환) */
	for (t = tmpA.begin(); t != tmpA.end(); t++) {
		check = B.find(*t);    
		if (check == B.end()) {	
			continue;
		}
		else {                 
			B.erase(check);     
		}
	}

	/* 3. 두 차집합 합치기
	   (1. A - B 연산을 통해 A는 A - B 형태로,
        2. B - A 연산을 통해 B는 B - A 로 변환되었음) */
	for (t = A.begin(); t != A.end(); t++) {
		check = B.find(*t);    
		if (check == B.end()) {	
			B.insert(*t);
		}
		else {                  
			continue;      
		}
	}

	/* 4. 두 차집합의 합집합의 원소의 개수 출력
	   (3에서 두 차집합 A, B를 B에 합쳤으므로, B의 원소들을 출력) */
	cout << B.size();         

	return 0;
}

우선, 위와 같이 변수들을 선언해준 뒤, 집합 A와 B의 원소의 개수와 각 원소들을 입력받는다.

여기서, 집합 A의 원소를 입력받을 때, 집합 A와 tmpA에 같은 값을 넣어주는데,

위에서 언급했듯, B - A 연산을 하는 과정에서 집합 A가 필요한데,

 A - B 연산을 하는 과정에서 집합 A의 값이 변화하기 때문에 A의 복사본(tmpA)이 필요하기 때문이다.

 

집합 A와 B의 원소들을 모두 입력받고 나면,

1. A - B 연산에서는 B의 원소를 A에서 찾고,

A에 없는 원소이면 남기고, 있는 원소이면 교집합 부분에 해당하므로 삭제한다.

이 과정에서, 집합 A에는 A - B 에 해당하는 원소들만 남게 된다.

 

2. B - A 연산에서는 A의 원소를 B에서 찾게 되는데,

A는 이미 A - B로 변환되었으므로, 위에서 생성한 복사본인 tmpA를 이용해

1. A - B 와 동일하게 연산을 해준다.

이 과정에서, 집합 B에는 B - A 에 해당하는 원소들만 남게 된다.

 

3. 두 합집합을 합치는 과정에서는,

A는 A - B, B는 B - A로 변환이 된 상태이므로, 두 집합을 비교한다.

A(A-B)의 원소를 B(B-A)에서 찾고,

B(B-A)에 없는 원소면 삽입, 있는 원소면 중복이므로 건너뛴다.

이 과정에서, 집합 B(B-A)에 모든 원소들이 합쳐지므로,

B에 두 차집합의 합집합의 원소들만 남게 된다.

 

위와 같은 연산들을 모두 완료하면,

집합 B가 곧 두 차집합의 합집합이 되므로, B의 원소들의 갯수(size)를 출력하면 된다.

 

 

---

즐거운 추석연휴가 끝났다..😭

다시 일상으로 돌아와서 또 빡세게 살아야지✍

앞으로 토요일을 14번만 더 보내면 2022년이라는데, 뭔가 기분이 싱숭생숭하다.

이번 1년이 너무 금방 지나가버린 느낌이랄까🤔

남은 한해 잘 마무리하고 하루하루 열심히 살아야지

 

+

 

주석 다는 연습을 좀 더 해야할 것 같다.

주석을 보기 편하고 이해하기 쉽도록 다는 연습!

주석이 너무 많으면 또 보기가 불편하고, 너무 없으면 코드를 이해하기가 힘드니..

관련된 책이라도 있으면 좋을것같은데, 한번 찾아봐야겠다.🧐