< 백준 BaekJoon : 1269번 대칭차집합> C++

<<문제>>

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

1269번: 대칭 차집합

두 집합의 대칭차집합의 개수를 구하는 문제.

 

<<풀이>>

굉장히 여러 가지 방법을 생각했습니다. 집합A 와 집합B의 원소들을 각각 다른 배열에 입력받고 비교하는 방법을 여러번 시도했는데, 메모리 초과를 벗어날 수 없었습니다.

 

그래서 생각한 방법이 벡터의 중복제거를 사용하는 방법입니다.

요런 느낌

1. A집합과 B집합의 원소들을 모두 한 벡터에 저장한다.

2. 저장한 벡터를 uique와 erase를 통해 중복을 제거한다.

 -  이때 이 함수들은 중복된 원소들은 한개만을 남겨둡니다.

3. A집합의 크기 + B집합의 크기  - 중복을 제거한 벡터의 크기  == 결국 중복된 원소의 수 이므로 A + B 에서 중복된 원소의 수 * 2를 빼줍니다.

 

<<코드>>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

/* BaekJoon1269: 대칭차집합
*/

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

	int numA, numB;
	cin >> numA >> numB;

	vector<int> vec(numA + numB, 0); // 한 벡터에 같이 저장
	for (int i = 0; i < numA + numB; i++) { cin >> vec[i]; }
	
	// A집합과 B집합의 중복된 값을 제거
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end()); 
	

	// numA + numB - vec.size() 는 결국 중복된 원소의 개수를 나타낸다.
	// 따라서 총 원소의 개수(numA + numB) 에서 중복된 원소의 개수*2 만큼 빼주면 정답 
	int result = numA + numB - (numA + numB - vec.size()) * 2;
	cout << result;
}

<<깃헙>>

https://github.com/J2on/BaekjoonOnlineJudge/blob/master/V2/BaekJoon_1269.cpp

GitHub - J2on/BaekjoonOnlineJudge: My Study