[BaekJoon] 1269 대칭 차집합

1.  문제 링크

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에 원소들을 넣을 수 있고, 탐색 시간을 줄여 시간 초과도 해결할 수 있었습니다.