[실버 4] 백준 1269 - 대칭 차집합 (파이썬)

https://www.acmicpc.net/problem/1269

풀이

1. A를 집합(set)으로 변환
   1. 집합을 사용하면 in 연산이 평균 시간 복잡도 O(1)로 빠르게 작동
2. B를 순회하며 A에 포함된 원소 개수를 센다.
3. 대칭 차집합 개수 계산
4. print(N + M - 2 * count)

시간 복잡도 분석

1. 집합 변환 (set) : O(N)
2. B 순회 및 포함 여부 확인 : O(M)
3. 최종 연산 : O(1)

최종 시간 복잡도 : O(N + M)

코드

# 백준 1269 - 대칭 차집합
# 분류 : 집합

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A = set(A)

count = 0
for b in B :
    if b in A :
        count += 1

print(N + M - 2 * count)