[JAVA] BOJ_1269. 대칭 차집합

🦅 문제

1269번: 대칭 차집합

---

🦍 문제 풀이

1. 무엇을 구해야 할까?

집합 A, B에 대해서 대칭 차집합 원소의 개수를 구해야한다.

여기서 대칭 차집합은 각각의 집합에 대한 차집합의 합집합이다.

(A-B) U (B-A)

 

2. 어떻게 구해야 할까?

입력받은 두 집합의 값들을 각각의 컬렉션에 담은 후, A가 가진 값들을 B가 가지고 있는지, 그리고 그 반대의 경우를 확인해주며 원소의 개수를 카운트해주면 된다.

 

3. 특별히 고려할 사항은?

1) 컬렉션의 선택

 - 단순히 A 집합의 값들이 B 집합에 존재하는지, 그리고 그 반대의 경우만을 고려해주면 된다. 따라서 HashSet이든, ArrayList든 contains 메서드만 이용해주면 풀이가 가능할 것이라고 생각할 지 모른다. 하지만, contains 메서드의 시간복잡도는 HashSet에서는 O(1)이지만, ArrayList에서는 O(n)의 시간복잡도를 가져 ArrayList로 풀이를 하면 시간초과가 난다. 따라서 각 자료구조의 특성을 우선적으로 이해해야 한다.

 

2) 값이 포함되어 있는지 확인하는 방법

 - 처음에는 HashSet의 add 메서드를 이용해, true를 반환하면 값이 없음을 나타내고 false를 반환하면 값이 존재한다는 점을 이용해 풀이했었다. true를 반환해 값이 들어간 경우에는 다시 이 값을 제거해주는 작업을 포함시켜 contains 메서드를 이용했을 때 보다 불필요한 작업이 한 단계 수행되었었다. 따라서, 어떤 방법을 이용해 확인을 할 수 있는지도 시간을 줄이는데 핵심적인 부분이다.

---

🐕‍🦺 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		
		// A, B 집합에 값 넣어주기
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		Set<Integer> arrA = new HashSet<>();
		Set<Integer> arrB = new HashSet<>();

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < A; ++i) {
			arrA.add(Integer.parseInt(st.nextToken()));
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < B; ++i) {
			arrB.add(Integer.parseInt(st.nextToken()));
		}

		// cnt : 원소의 개수를 저장할 변수
		int cnt = 0;
		
		// 집합 B에 집합 A의 원소가 들어가있는지 확인 후 카운트
		for (int a : arrB) {
			if (!arrA.contains(a)) {
				++cnt;
			}
		}

		// 집합 A에 집합 B의 원소가 들어가있는지 확인 후 카운트
		for (int i : arrA) {
			if (!arrB.contains(i)) {
				++cnt;
			}
		}
		
		// 정답 출력
		System.out.print(cnt);
	}
}

---

1. HashSet과 contains 메서드를 이용한 풀이 (712 ms)

2. HashSet과 add 메서드를 이용한 풀이 (836 ms)

---

🐖 Think

- 보다 기본에 충실해야겠다는 생각을 가지게 한 문제였다. 풀이 자체는 어렵지 않으나 여러가지 풀이 방법들이 존재하는 문제들을 보다 효율적으로 풀이해보겠다 하는 마음가짐이 필요한 것 같다.