[Python] 백준 1764번 - 듣보잡 / set 집합

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

 

---

딱보면 두 배열을 비교하여 일치하는 개수와 일치하는 명단을 출력하는 간단한 문제이다.

 

하지만 문제가 있다.

 

단순히 리스트에 저장하여 비교를 하기엔 N과 M의 최대 크기가 500,000이다.

 

즉 단순히 값에 넣고 저장하여 비교를 돌리면 58000% 확률로 시간 초과를 보게 될 것이다.

 

그렇다면 무언가 기술적으로 사용해야 한다는 것인데... 난 몰라서 검색했다.

 

집합 자료형 ( set )

 

우선 이 문제를 풀기 위해서는 집합 자료형에 대해서 알아야 한다.

 

2022.01.04 - [Language/Python] - [Python] 자료형, list, tuple, set, dict / 예제로 공부하는 Python 100 문제풀이

[Python] 자료형, list, tuple, set, dict / 예제로 공부하는 Python 100 문제풀이

이땐 단순한 방법만 배웠기 때문에 모를만 하다.

 

집합 자료형은 두 집합 간의 비교 및 연산이 가능하다.

 

우선 예시로

 

s1 = {1, 2, 3, 4, 5, 6}

s2 = {4, 5, 6, 7, 8, 9}

 

위의 두 집합이 있다고 가정하겠다.

 1. 교집합

'&', intersection()

 

s1 & s2

 - {4, 5, 6}

s1.intersection(s2)

 - {4, 5, 6}

 

2. 합집합

'|', union()

 

s1 | s2

s1.union(s2)

 - {1, 2, 3, 4, 5, 6, 7, 8, 9}

 

3. 차집합

'-', difference()

 

s1 - s2

s1.difference(s2)

 - {1, 2, 3}

 

s2 - s1

s2.difference(s1)

 - {7, 8, 9}

 

이 외에 

 

s1.add(10)

s1.update([11, 12, 13])

s1.remove(3)

 

추가/수정/삭제 방법도 있다.

 

이제 set에 대해 어느 정도 알아봤으니 풀이는 쉽다.

---

import sys
n, m = map(int, sys.stdin.readline().split())
a = set()
for _ in range(n):
  a.add(sys.stdin.readline().rstrip())
b = set()
for _ in range(m):
  b.add(sys.stdin.readline().rstrip())

c = sorted(list(a & b))
print(len(c))
for i in c:
  print(i)

집합 a, b를 선언하여 값을 채워 준 후

 

a 와 b의 교집합을 리스트 c에 사전 순으로 출력하기 위해 정렬된 형태로 저장하여 출력한다.

 

참고

https://wook-2124.tistory.com/476

https://velog.io/@inyong_pang/Python-List-Tuple-Dictionary-and-Set-%EC%9A%94%EC%95%BD