[Baekjoon/백준] 1269번: 대칭 차집합(C/C++)
단계별로 풀어보기 12단계(집합과 맵) 6번 문제
https://www.acmicpc.net/step/49
집합과 맵 단계
카드의 집합을 만들어 특정 카드가 집합에 있는지 빠르게 찾는 문제
www.acmicpc.net
백준 1269번: 대칭 차집합
https://www.acmicpc.net/problem/1269
1269번: 대칭 차집합
첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어
www.acmicpc.net
문제 설명
자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.
예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.
입력과 출력
입력: 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.
출력: 첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

접근 방법
이번 문제는 집합 A와 B의 원소 개수를 입력받고, A개의 집합 원소들과 B개의 집합 원소들을 입력받아서 대칭 차집합의 원소 개수를 출력하는 문제다. 대칭 차집합은 A와 B의 공집합을 제외한 원소들의 집합이다. 쉽게 말해서 A 집합, B집합만 가지고있는 원소들을 합한것이라고 보면 된다.
지난 문제와 비슷하게 원소(int)를 키로 하고 int를 값으로하는 map과 int를 사용하는 vector 2개를 이용해서 풀면 된다.
숫자를 입력받아서 map[num]++을 하고 vector1에 모두 push 한다. 이후 B의 원소를 입력 받을때도 map[num]++를 해서 만약 map[num]이 1을 초과하면 vector1을 pop하고, 1과 같다면 vector2에 push 한다. 이후 두 vector의 size를 더해 출력하면 문제를 해결할 수 있다.
사실 vector1을 위 방법처럼 push하고 pop하면 집합 A의 원소가 차집합이 남는 것은 아니지만, 어차피 원소의 개수를 계산하는 것이므로 이렇게 풀어도 해결은 된다.
코드
#include <iostream>
#include <map>
#include <vector>
using namespace std;
map<int, int> m;
vector<int> v1;
vector<int> v2;
int main(int argc, char * argv[]) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int A, B, num;
cin >> A >> B;
for (int i = 0; i < A; i++) {
cin >> num;
m[num]++;
v1.push_back(num);
}
for (int i = 0; i < B; i++) {
cin >> num;
m[num]++;
if (m[num] > 1)
v1.pop_back();
else if (m[num] == 1)
v2.push_back(num);
}
cout << v1.size() + v2.size() << endl;
return 0;
}
결과
