[백준/Python] 듣보잡

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

1764번: 듣보잡

[ 처음 코드 ] - 시간 초과

n, m = map(int, input().split())

not_listen = [input() for _ in range(n)]
not_look = [input() for _ in range(m)]

# 듣보잡 구한 후  사전 순으로 정렬
result = [i for i in not_listen if i in not_look]
result.sort()

print(len(result))
for r in result:
	print(r)

처음 코드가 풀이는 맞으나 시간 초과가 발생했다. 원인은 듣보잡을 구하는 부분에서 중복을 찾는 것 때문이었다. in 은 시간복잡도가 O(N)이라서 결국 듣보잡을 구할 때 시간복잡도가 O(N^2)이 되므로 시간초과가 발생하는 것이었다. 따라서 시간 초과를 해결하기 위해 not_listen과 not_look 을 집합으로 바꾼 후 교집합 연산자(&)를 사용해 중복을 찾았다.

 

[ 최종 코드 ]

n, m = map(int, input().split())

not_listen = [input() for _ in range(n)]
not_look = [input() for _ in range(m)]

# 듣보잡 구한 후  사전 순으로 정렬
result = list(set(not_listen) & set(not_look))
result.sort()

print(len(result))
for r in result:
	print(r)