[자료구조/해시] 백준 1764 듣보잡 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1764번: 듣보잡

 

 

 

2. 문제 풀이

 두 집합의 교집합을 사전순으로 정렬하는 문제입니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 듣도 못한 사람과, 보도 못한 사람의 교집합을 구하는 문제입니다. (듣보잡)

 두 명단을 리스트로 받아서 비교할 수도 있지만, 시간초과를 면하지 못합니다..

 그 보다는 파이썬의 '집합' 자료구조를 사용해야 합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
noHear = [] #듣도 못한 사람
noHearSee = [] #듣보잡
for _ in range(N):
    noHear.append(input().rstrip())
for _ in range(M):
    noSee = input().rstrip() #보도 못한 사람
    if noSee in noHear:
        noHearSee.append(noSee)

noHearSee.sort() #사전순 정렬
print(len(noHearSee))
for name in noHearSee:
    print(name)

 본래는 in연산자로 비교해서 듣도보도 못한 사람들의 명단을 구했습니다. 하지만, 위 방식은 시간초과가 납니다.

 

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
noHear = set() #듣도 못한 사람
noSee = set() #듣보잡
for _ in range(N):
    noHear.add(input().rstrip())
for _ in range(M):
    noSee.add(input().rstrip()) #보도 못한 사람

noHearSee = sorted(list(noHear & noSee)) #교집합 중 사전순 정렬

print(len(noHearSee))
for name in noHearSee:
    print(name)

 파이썬의 집합 자료구조를 이용하면, 쉽게 구할 수 있습니다.