[baekjoon] 백준 10816번 : 숫자카드2 (by python 파이썬)

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

10816번: 숫자 카드 2

 

code

#숫자 카드2

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
dic1 = dict()

for i in a:
    if i in dic1:
        dic1[i] += 1
    else:
        dic1[i] = 1


m = int(input())
b = list(map(int,input().split()))

for i in b:
    if i in dic1:
        print(dic1[i],end=' ')
    else:
        print(0, end=' ')

 

시간초과 code

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))

m = int(input())
b = list(map(int,input().split()))

for i in b:
    count = 0
    for j in a:
        if i == j:
            count += 1
    print(count,end=' ')

처음 작성한 코드는 이중 for문을 통해 하나하나 탐색해나갔는데 이 과정에서 시간초과가 떴다.

 

 

그래서 새로 작성한 코드는 상근이가 가지고 있는 코드 a를 입력받고

바로 총 갯수를 파악한 후에 딕셔너리로 key와 벨류에 해당 숫자와 총 갯수를 넣어주었다.

 

그 후 입력받은 숫자카드에 대해 딕셔너리에 이미 저장해둔 값을 찾아 출력하는 방식으로 시간초과를 해결하였다.

 

리스트탐색에서는 시간복잡도 O(n)이 소요되지만

 

딕셔너리에서는 O(1)의 시간이 걸리므로 딕셔너리에 미리 카운트를 해두고 탐색함으로써 

시간을 줄였다.