백준 알고리즘 문제 풀이 1764 : 듣보잡

 

 

1764번: 듣보잡

 

---

문제

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

입력

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

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

출력

 

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

 

---

풀이과정

처음에는 직관적으로, 두 List에 듣 과 보 를 받아서 명단을 읽는 방식으로 처리하려했다.

다만 이 문제를 풀면서 처음으로, 시간초과 오류를 접하게되어 이 방식은 더이상 사용할 수 없게 되었다.

 

 

Dictionary와 처리속도

dictionary를 자료구조 기초단계에서 배우지만, 사실 사용하게 될줄 몰랐다.

Value와 Key로 구분된 쌍을 Data로 갖는 집합이며 사용방식도 간단한데, Key를 주면 Value를 뱉어낸다.

 

시간복잡도 (O(n) / O(1))

 

어떤 List에서 i번째 요소를 가져오는데 걸리는 시간 : O(1)

 -> n개의 요소를 가져오는데 걸리는 시간은 O(n)

 -> A List의 n개 요소와 B List의 m개 요소를 비교하는데 걸리는 시간은 O(n2)

value에 2가된것만 읽는 속도가 O(n)으로 O(n2) 인 List 비교방식보다 월등히 빠르다

 

그래서 인물 이름을 처음에 Key로 받고, 한번 더 입력되는 인물에 한하여 Value를 늘려주는 방식으로 구분해서 시간 초과 문제를 해결할 수 있었다.

 

 

Code

 

a, b = input().split()

dic = {}

for i in range(int(a)+int(b)):
    emeqh=input()
    if emeqh not in dic:
        dic[emeqh]=1
    else:
        dic[emeqh]=2

emeqhwkq=[]
for key, value in dic.items():
    if value==2:
        emeqhwkq.append(key)

print(len(emeqhwkq))
emeqhwkq.sort()

for i in emeqhwkq:
    print(i)