[BOJ #1764] 듣보잡

문제

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

 

입력

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

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

 

출력

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

 

내가 쓴 코드 1 (틀림)

from sys import stdin; input = stdin.readline
N, M = map(int, input().split())
arr1 = [input() for _ in range(N)]
arr2 = [input() for _ in range(M)]
arr3 = []
for i in range(N):
    if arr1[i] in arr2:
        arr3.append(arr1[i])

print(len(arr3))
arr3 = sorted(arr3)
for i in range(len(arr3)):
    print(arr3[i], end='')

 

내가 쓴 코드 2 (맞.)

from sys import stdin; input = stdin.readline
N, M = map(int, input().split())
arr1 = [input() for _ in range(N)]
arr2 = [input() for _ in range(M)]
arr3 = arr1 + arr2
set_arr3 = set(arr3)

for i in set_arr3:
    if i in arr3:
        arr3.remove(i)

print(len(arr3))
arr3 = sorted(arr3)
for i in range(len(arr3)):
    print(arr3[i], end='')

 

내가 쓴 코드 3 (맞. 미량이코드 참고)

from sys import stdin; input = stdin.readline
N, M = map(int, input().split())
arr1 = set(input() for _ in range(N))
arr3 = []
for i in range(M):
    compare = input()
    if compare in arr1:
        arr1.remove(compare)
        arr3.append(compare)

print(len(arr3))
arr3 = sorted(arr3)
for i in range(len(arr3)):
    print(arr3[i], end='')

 

제출 결과

나의 생각대로 쉬운 편인 문제였지만,, 시간초과와의 사투를 벌였다..! 시간 초과 나서 미량이한테 힌트 달라고 해서 푼 게 '코드2' 이고, 미량이 코드를 보고 나서 풀어 본 게 '코드3' 이다. 근데 제출 결과를 보면 알 수 있듯, 코드2와 코드3의 시간 차가 미쳤다. 미량인 천재인가보다... 어떻게 저렇게 풀지,, 나는 시간 초과 났을 때 set() 으로 해결했던 적이 잘 없는 것 같은데, 미량인 무조건 시간초과 나면 set()을 최대한 이용해 풀어보려고 한다고 한다. 나도 앞으로는.. set()을 적극 이용해보게써!