백준 10816 숫자카드 2 - 딕셔너리

10816번: 숫자 카드 2 (acmicpc.net)

10816번: 숫자 카드 2

어떤 숫자들에 상근이의 숫자가 몇번이나 포함되었는가를 구하는 문제였는데

보자마자 딕셔너리로 풀어야겠다! 가 떠올랐다.

하지만 계속 시간초과가 나게 되고..

 

<시간초과 코드>

import sys

N = int(input())
lst = list(map(int, sys.stdin.readline().split()))
M = int(input())
lst2 = list(map(int, sys.stdin.readline().split()))
dic = {}
for j in range(N):
    if lst[j] in lst2:
        if lst[j] not in dic :
            dic[lst[j]] = 1
        else:
            dic[lst[j]] += 1
print(' '.join(str(dic[i]) if i in dic else '0' for i in lst2))

이 전에도 이중 포문을 돌리거나 여러 방식으로 했었는데 시간초과가 나더라.

내가 보기에는 if in -> 이게 시간복잡도가 큰듯...

 

<맞은 코드>

import sys

N = int(input())
lst = list(map(int, sys.stdin.readline().split()))
M = int(input())
lst2 = list(map(int, sys.stdin.readline().split()))
dic = {}
for j in range(N):
    if lst[j] not in dic :
        dic[lst[j]] = 1
    else:
        dic[lst[j]] += 1
print(' '.join(str(dic[i]) if i in dic else '0' for i in lst2))

이렇게 if in을 한 번만 써서 그때만 dictionary에 요소를 추가하고 그렇지 않을 때에는 그냥 0을 출력하는 식으로 구하면 시간초과가 뜨지 않는다.

딕셔너리의 구조, 접근법을 더 정확히 알고 있으면 한번에 맞출 수 있었을 듯..

 

print(' '.join(str(dic[i]) if i in dic else '0' for i in lst2))

이런 길지만 한번에 출력 가능한 리스트 컴프리헨션도 익혀두자!