[BackJoon] 1764번 듣보잡

전체 문제 보기

문제

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

입력

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

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

출력

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

풀이

1. 입력의 크기가 50만개이므로 이중반복문으로 사용할 때 시간초과가 발생한다.
2. 딕셔너리를 사용해 시간복잡도를 줄여서 탐색을 한다.

첫번째 제출

# Backjoon 듣보잡

N, M = map(int, input().split())
name_list = []
for _ in range(N+M):
    name = input()
    name_list.append(name)
listen_dict = {}
see_dict = {}
for idx, name in enumerate(name_list):
    if idx < N:
        listen_dict[name] = 1
    else:
        see_dict[name] = 1

check_list = []
for check in listen_dict:
    if check in see_dict:
        check_list.append(check)

print(len(check_list))
for name in sorted(check_list):
    print(name)

set을 사용한 방법

N, M = map(int, input().split())
name_list = []
for _ in range(N+M):
    name = input()
    name_list.append(name)

# set()을 사용하여 집합으로 변경
listen = set(name_list[:N])
see = set(name_list[N:])
result = sorted(set(listen) & set(see)) # 집합의 연산으로 교집합 구하기

print(len(result),'\n'.join(result),sep='\n')