[Algorithm] 백준 정렬 알고리즘 - 1764번 듣보잡 풀이

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

1764번: 듣보잡

보통 처음 생각하는 풀이는

둗도 못한 사람의 수 N개의 이름을 담은 리스트를 입력받고

보도 못한 사람의 수 M개의 이름을 입력받으면서

듣도 못한 사람의 수 리스트에 이미 이름이 있으면 결과 리스트에 담아서 정렬을 하면 된다고 생각한다.

 

하지만!!

그렇게 하면 시간초과가 뜬다 (N,M이 최대 500000이기 때문에)

 

그래서 나의 풀이는 다음과 같다

n, m = map(int,input().split())
result={}
for _ in range(n+m):
    data = input()
    if data in result.keys(): #듣도 못한 사람과 보도 못한 사람이 중복된다면 +1
        result[data]+=1
    else:
        result[data]=1
result2=[]
for key,item in result.items():
    if item == 2:	#듣도보도못한 사람을 결과 리스트에 담는다
        result2.append(key)
result2.sort()
print(len(result2))
print('\n'.join(result2))

파이썬의 딕셔너리를 사용해서 리스트의 비교 없이

딕셔너리의 key, item 속성을 이용해서 듣보잡 이름을 거르고 정렬하여 출력한다