백준 1764번- '듣보잡' (PYTHON 풀이, 문제 해석 O)

문제:

문제를 처음 읽었을 때 이해를 못해서 서치를 통해 문제 이해부터 진행하였다.

결과적으로 해당 문제는 듣도 못한 사람들과 보도 못한 사람들을 따로 분류해서 두 곳에 모두 해당하는 사람의 수와 그 사람 이름을 출력하면 되는 문제이다!

 

예를 들어, [듣도 : 동해, 물과, 백두]가 있고 [보도: 동해, 산이, 백두] 이렇게 있다면 겹치는 사람은 동해와 백두로 2명이니까 2가 출력되고 각 이름이 출력되면 된다.

 

 

풀이:

N, M = map(int,input().split())
dic1 = {}
dic2 = {}
count = 0
result = []

for i in range(N):
    dic1[input()] = 1

for j in range(M):
    dic2[input()] = 1

sorted_result = sorted(dic2)

for k in sorted_result:
    if k in dic1:
        count += 1
        result.append(k)

print(count)
for w in result:
    print(w)

원래 이 문제를 이중 for문으로 풀려고 했는데, 보나마나 시간초과가 뜰 것 같아서 시도 하지 않고 다른 방법으로 어떻게 풀지 고민하였다.

그러다 이번주에 많이 사용한 딕셔너리를 풀면 시간 초과 없이 풀 수 있을 것 같아서 이를 활용하기로 하였다.

사실 위 코드에서 보면 알다시피 딕셔너리의 역할을 크게 없다. 그러나 딕셔너리로 풀면 이중 for문으로 풀 때마다 시간이 훨씬 빨라 시간 초과 없이 문제를 풀 수 있다.

코드 자체는 단순하다. 사용자로부터 입력받은 값만큼 반복문을 돌아서 딕셔너리에 이름을 차곡차곡 쌓고, if문을 활용해 두 딕셔너리를 비교해서 일치하면 count를 1 더하고 마지막엔 이를 출력한 뒤, 이름까지 출력 형식에 맞게 한 줄 띄워서 출력해주면 된다.

 

아, 참고로 문제는 이렇게 풀었는데 딕셔너리 대신 리스트를 넣어서 풀면 되지 않냐고 생각하시는 분들이 계실 것 같아 직접 코드를 리스트로 바꿔서 백준에 다시 시도해보았다. 하지만 역시나 시간초과가 뜬다.

 

기본적으로 리스트와 딕셔너리는 아래와 같은 특징을 갖고 있다.

리스트는 배열로서, 순차 탐색으로 앞에서 하나씩 비교해서 일치하는지 확인하기 때문에 O(N)의 시간복잡도를 갖는다면, 딕셔너리는 해시 테이블을 활용하여 O(1)의 시간복잡도를 갖는다. 그러니 당연히 시간초과가 날 수 밖에..

list	배열(Array)	앞에서부터 하나씩 비교 (==)	O(N)
dict	해시 테이블(Hash Table)	키 → 해시함수 → 주소 바로 접근	O(1) 평균

 

이중 for문, 리스트로 시간초과가 난다면 딕셔너리를 활용하면 좋을 것 같다.