[백준 알고리즘] 1764번: 듣보잡 (Python)

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

1764번: 듣보잡

 

문제

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

입력

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

출력

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

 

소스코드

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
p = dict()
ans = []
for i in range(n):
  word = input().strip()
  p[word] = 1

for i in range(m):
  word = input().strip()
  if word in p.keys():
    p[word] = 2

for key,val in p.items():
  if val == 2:
    ans.append(key)

print(len(ans))
ans.sort()
for x in ans:
  print(x)

 

풀이

제목이 재밌어서 한번 풀어봤던 문제입니다 ! 
처음에 해쉬가 아닌 다른 방법으로 문제를 풀었는데, 입력 값이 크다보니 시간 초과가 발생하였고, 해쉬와 정렬을 사용해 코드를 작성하니 무난하게 맞췄던 문제입니다 !
 
'해쉬'라 함은 파이썬의 딕셔너리 자료형입니다. 그와 관련된 자료는 다음 사이트를 참고하시면 좋을 거 같습니다
 
https://yunaaaas.tistory.com/46

[Python 자료구조] Hash(해시)

 
듣도 못한 사람인 n개의 문자열을 입력 받을 때 그 문자열을 딕셔너리의 key로 저장하고 value를 1로 설정해줍니다.
그 후 보도 못한 사람인 m개의 문자열을 입력 받을 때 이미 그 문자열이 딕셔너리의 key로 존재한다면 value를 2로 변경해줍니다 ! 
 
그 후 key,value 반복문을 돌면서 value의 값이 2인 값을 리스트에 저장해주고, 
출력을 알파벳 순으로 출력해야 하기에 리스트를 오름차순으로 sort() 해줍니다 !
 
그 후 리스트를 반복문으로 돌며 출력을 해주시면 됩니다 :)