boj 1764 : 듣보잡

문제 주소: https://www.acmicpc.net/problem/1764

난이도: silver 4

1.문제설명

• 듣지못한사람 이름이 주어진다
• 보지못한사람 이름이 주어진다.
• 듣도 보지도못한사람의 수와, 이름을 사전순으로 출력한다.

2.문제해결 아이디어.

• 시간복잡도를 고려해서 어떻게 듣지도 보지도 못한 사람을 체크하냐가 중요하다.
• 리스트를 두개써서 겹치는 사람을 찾는건 시간초과가 날 것이다.
• default dict를 사용해보자

3.문제접근법

• default dict를 이용해 듣지못한사람, 보지못한사람을 기록한다.

name_dict = defaultdict(int)
for i in range(N):
    name = input().rstrip()
    name_dict[name] += 1

• 이렇게 해주면 딕셔너리에 처음 추가되는 key의 value는 0으로 세팅된다.

name_list = [item for item in name_dict.items() if item[1] > 1]
name_list.sort(key= lambda x : x[0])

• 파이썬의 강점인 list comprehension을 사용해 듣보잡인 사람들을 걸러내서 리스트로 만들어준다.
• 그리고 이름순으로 정렬해준다.

4.특별히 참고할 사항

• default dict, counter 등은 문자열 문제에 많이 쓰일것 같으니, 익숙해지거나 최소한 존재를 알고있자.

5.코드구현

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().rstrip().split())
name_dict = defaultdict(int)
for i in range(N):
    name = input().rstrip()
    name_dict[name] += 1
for i in range(M):
    name = input().rstrip()
    name_dict[name] += 1
name_list = [item for item in name_dict.items() if item[1] > 1]
name_list.sort(key= lambda x : x[0])
print(len(name_list))
for item in name_list:
    print(item[0])