백준1822번 파이썬 문제풀이(차집합)

---

1. set 함수 집합의 연산을 이용하여 풀기

nA, nB = map(int, input().split())

A = set(map(int, input().split()))
B = set(map(int, input().split()))

print(len(A - B))  # 차집합의 길이를 출력
print(*sorted(list(A - B)))  # 차집합의 원소를 출력

---

 

2.  Hash함수(딕셔너리)를 이용하여 풀기

a, b = map(int, input().split())
A, B = {}, {}
for n in map(int, input().split()):
    A[n] = 1
for n in map(int, input().split()):
    B[n] = 1

# 리스트로 풀면 시간초과가 나지만 해쉬로 풀면 문제를 해결할 수 있다.
C = []
for i in A:
    if i not in B:
        C += [i]

print(len(C))
print(*sorted(C))

-> 리스트로 반복문을 돌면 시간초과가 나지만 딕셔너리로 돌면 시간초과가 발생하지 않는다. 그 이유는 딕셔너리의 대부분 연산의 시간복잡도는 O(1)이며 특히 위의 if i not in B: 구문에서 리스트와 시간차이가 발생한다.