(Python)백준 코딩테스트 연습 - 듣보잡(1764)

1. 문제

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

1764번: 듣보잡

2. 풀이

import sys
input = sys.stdin.readline

# n : 듣도 못한 사람 수, m : 보도 못한 사람 수
n, m = map(int, input().split())

# n_l : 듣도 못한 사람 set
n_l = set([input() for i in range(n)])

# m_l : 보도 못한 사람 set
m_l = set([input() for i in range(m)])

# nm_l : 듣도 보도 못한 사람 list
nm_l = list(n_l.intersection(m_l))
nm_l.sort()

print(len(nm_l))
for i in nm_l:
    print(i.strip())

3. 후기

 - 처음 문제를 봤을때 바로 듣 생각은 먼저 입력받은 듣도 못한 사람 이름을 리스트로 만든 후 다음에 입력받는 보도 못한 사람들이 입력될 때마다 듣도 못한 사람 리스트를 조회하여 있다면 새로운 리스트에 추가하는 형태를 생각했다. 하지만 당연히 사람 수가 최대 500,000까지 입력되는 조건에서 최대 500,000의 제곱까지 시간 복잡도가 늘어나기 때문에 다른 형태를 생각하게 됐다. 다음으로 생각한 방식은 교집합이다. 교집합 또한 코드로 충분히 구현이 가능하고 시간 복잡도 또한 낮기 때문에 해결 가능했다.

 추가로 sys를 이용한 입력은 \n이 포함되어 있음을 잊지 말자, strip()을 안쓰니 출력 형식 오류가 뜬다.