문제
두 집합 A, B가 주어질 때, 대칭 차집합 (A-B) ∪ (B-A)의 원소 개수를 구하라.
입력
첫째 줄에 A의 크기와 B의 크기(각각 200,000 이하), 둘째 줄에 A의 원소, 셋째 줄에 B의 원소가 주어진다. 원소 값은 1억 이하 자연수.
출력
대칭 차집합의 원소 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 5 1 2 4 2 3 4 5 6 | 4 |
풀이
HashMap을 이용하여 교집합의 크기를 구한 뒤, |A| + |B| - 2 * |A ∩ B|로 대칭 차집합 크기를 계산한다.
- A의 원소를 HashMap에 저장한다
- B의 원소를 순회하며 HashMap에 존재하는 원소(교집합)의 개수를 센다
- 대칭 차집합 = |A| + |B| - 2 * 교집합 크기
핵심 아이디어: 대칭 차집합은 두 집합에서 공통 원소를 제거한 것이므로, 교집합 크기만 구하면 O(1)로 답을 계산할 수 있다.
코드
package com.ssafy.an.day199;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Day160BOJ1269대칭차집합해쉬 { // 1269 대칭 차집합
static int A, B;
static HashMap<Integer, Integer> hashMap = new HashMap<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Integer.parseInt(st.nextToken());
B = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < A; i++) {
hashMap.put(Integer.parseInt(st.nextToken()), i);
}
int dup = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < B; i++) {
int key = Integer.parseInt(st.nextToken());
if (hashMap.containsKey(key))
dup++;
}
System.out.println(A + B - dup - dup);
}
}복잡도
- 시간: O(A + B)
- 공간: O(A)