[Python] 백준 1764번 - 듣보잡

문제 링크 : https://www.acmicpc.net/problem/1764

1764번: 듣보잡

문제

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

입력

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

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

출력

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

 

예제 입력 :

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 : 

2
baesangwook
ohhenrie

 

코드

N, M = map(int, input().split())

hear_see = []

hear = [input().strip() for i in range(N)]
see = [input().strip() for j in range(M)]

hear_see = list(set(hear)&set(see))

hear_see.sort()
print(len(hear_see))
for x in range(len(hear_see)):
    print(hear_see[x])

 

+ 기억해두기 

 

1. input()으로 받지 말고

import sys
input = sys.stdin.readline

을 사용하는게 훨 빠르다. 

위 readline, 아래 그냥 input()

readline 안해주고 input()이렇게 했는데 시간초과 안뜨고 되긴 했는데
그래도 쓰는게 빠르니까 그렇게 하자.

 

2. hear = [input().strip() for i in range(N)]
나는

for i in range(N):
	hear.append(input())

이렇게 했는데 저렇게 간추려서 하는게 훨 낫다!
그리고 문제에서 띄어쓰기가 없다고 했으니 strip()사용~

3. hear_see = list(set(hear)&set(see))

나는 중복되는 문자열을 찾을 때

for i in hear:
 if i in see:
   hear_see.append(i)

이런 식으로 코딩했는데 이렇게 하면 역시나 시간초과!
교집합을 이용하도록 하자~
set(s1) & set(s1)
s1.intersection(s2)
두가지 표현으로 가능!