1. 문제 링크
https://www.acmicpc.net/problem/1269
2. 문제

요약
- 대칭 차집합이란 두 집합 A,B에 대해서 A - B와 B - A의 합집합을 의미합니다.
- 주어진 두 집합 A,B에 대한 대칭 차집합의 원소의 개수를 구합니다.
- 입력: 첫 번째 줄에는 두 집합 A, B의 원소의 개수가 주어지고 두 번째 줄에는 집합 A의 원소들이, 세 번째 줄에는 집합 B의 원소들이 주어집니다.
- 출력: 두 집합 A, B의 대칭 차집합의 원소의 개수를 출력합니다.
3. 소스코드
초기 버전
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Main {
public int getNumSet(int num_a, int num_b, String list_a, String list_b) {
ArrayList<Integer> component_a = new ArrayList<Integer>();
ArrayList<Integer> component_b = new ArrayList<Integer>();
ArrayList<Integer> copy_a = new ArrayList<Integer>();
ArrayList<Integer> copy_b = new ArrayList<Integer>();
StringTokenizer st = new StringTokenizer(list_a);
for(int i = 0; i < num_a; i++) {
component_a.add(Integer.parseInt(st.nextToken()));
copy_a.add(component_a.get(i));
}
st = new StringTokenizer(list_b);
for(int i = 0; i < num_b; i++) {
component_b.add(Integer.parseInt(st.nextToken()));
copy_b.add(component_b.get(i));
}
copy_a.removeAll(component_b);
copy_b.removeAll(component_a);
copy_a.addAll(copy_b);
HashSet<Integer> set = new HashSet<Integer>(copy_a);
return set.size();
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String nums = br.readLine();
StringTokenizer st = new StringTokenizer(nums);
int num_a = Integer.parseInt(st.nextToken());
int num_b = Integer.parseInt(st.nextToken());
String list_a = br.readLine();
String list_b = br.readLine();
br.close();
Main m = new Main();
bw.write(m.getNumSet(num_a, num_b, list_a, list_b));
bw.flush();
bw.close();
}
}
수정 버전
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
public int getNumSet(int num_a, int num_b, String list_a, String list_b) {
ArrayList<Integer> component_a = new ArrayList<Integer>();
ArrayList<Integer> component_b = new ArrayList<Integer>();
StringTokenizer st = new StringTokenizer(list_a);
for(int i = 0; i < num_a; i++) {
component_a.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(list_b);
for(int i = 0; i < num_b; i++) {
component_b.add(Integer.parseInt(st.nextToken()));
}
TreeSet set = new TreeSet();
for(int i = 0; i < component_a.size(); i++) {
if(!set.add(component_a.get(i))) {
set.remove(component_a.get(i));
}
}
for(int i = 0; i < component_b.size(); i++) {
if(!set.add(component_b.get(i))) {
set.remove(component_b.get(i));
}
}
return set.size();
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String nums = br.readLine();
StringTokenizer st = new StringTokenizer(nums);
int num_a = Integer.parseInt(st.nextToken());
int num_b = Integer.parseInt(st.nextToken());
String list_a = br.readLine();
String list_b = br.readLine();
br.close();
Main m = new Main();
bw.write(m.getNumSet(num_a, num_b, list_a, list_b) + "\n");
bw.flush();
bw.close();
}
}
4. 접근
- 두 집합 A와 B에서 겹치는 원소들을 뺀 나머지 원소들의 개수를 구하면 됩니다.
- 초기 버전에서는 removeAll을 통하여 두 집합에서 겹치는 부분을 각각 빼준 후, 이 두 집합을 addAll을 통해 합쳐 합친 집합의 개수를 출력하였습니다.
- 그러나 removeAll을 실행할 때, 서로 겹치는 원소를 찾은 후에 해당 원소들을 제거해줘야 하는데 이 때, 탐색하는 시간이 너무 오래 걸려서 시간 초과가 되었습니다.
- 탐색하는 시간을 줄이기 위해 탐색을 더 빠르게 할 수 있는 자료구조인 TreeSet을 이용하였습니다.
- 두 집합 A와 B의 원소들을 TreeSet에 추가하는데, TreeSet에 없는 원소를 추가하면 해당 원소를 추가하고 True를 리턴하고, TreeSet에 있는 원소를 추가하면 False를 리턴하기 때문에 이를 이용하여 이미 있는 원소를 추가할 때 해당 원소를 제거하는 방식으로 TreeSet에 원소들을 추가하였습니다.
- 이 방법으로 TreeSet에 추가하면 겹치는 원소를 제외하고 TreeSet에 원소들을 넣을 수 있고, 탐색 시간을 줄여 시간 초과도 해결할 수 있었습니다.