백준:10816(Python)

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

 

import sys
n = int(sys.stdin.readline())
list1 = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
list2 = list(map(int, sys.stdin.readline().split()))
list2_m = [0]*m

list2_dict = dict(zip(list2, list2_m))

for i in list1:
    if i in list2:
        list2_dict[i] += 1
    
for value in list2_dict.values():
    print(value, end=' ')

 

계산 시간 : 2460ms

 

풀이가 틀린 이유를 살펴보자면 전에 풀었던 문제가 리스트로 문제를 풀면 시간이 초과되고 딕셔너리로 풀면 되는 문제였다. 그래서 딕셔너리를 이용했는데 딕셔너리를 사용하여 문제를 풀 때의 핵심은 단순히 딕셔너리를 사용하는 것이 아니라 딕셔너리를 통해 비교하는 과정에서 리스트를 배제하고 딕셔너리로 문제를 풀어야 한다는 것이었다.

따라서 비교 과정에서 딕셔너리만 사용하여 문제를 풀어보았다.

 

import sys
n = int(sys.stdin.readline())
list1 = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
list2 = list(map(int, sys.stdin.readline().split()))

n_dict ={}

for n in list1:
    if n in n_dict:
        n_dict[n] += 1
    else:
        n_dict[n] = 1

for m in list2:
    if m in n_dict:
        print(n_dict[m], end = ' ')
    else:
        print(0, end=' ')

코드 실행 시간 : 760ms

가장 중요한 부분은 for문으로 순회할 때는 list가 있어도 상관없지만 if문으로 참, 거짓 판별을 해줄 때는 if로 딕셔너리를 도는 것이 핵심이었다.

 

# 참고

https://all-knowledge-of-the-world.tistory.com/17

[Python] Dictionary를 이용해 데이터를 빠르게 검색하고 타이머로 시간을 측정해 보자!

딕셔너리로 이용하는 것이 빠르다는 것을 알 수 있는 블로그이다.