[백준 10816번 파이썬] 숫자 카드2

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

10816번: 숫자 카드 2

 

 

 문제 풀이

문제를 보면 for문을 두번 돌려서 하면 되겠구나.. 했는데 

난 백준이 던진 미끼에 낚였다....덕분에 이제 시간 복잡도에 대해서 생각하게 되었다.

적당히 범위를 줬겠지 했는데 계산해보니까 500,000 *500,000= 2,500억 횟수...ㅎㄷ

N(1 ≤ N ≤ 500,000) M(1 ≤ M ≤ 500,000) 각각의 범위 

 

시간 복잡도 때문에 문제를 다시 생각했다.

 

a= 6,3,2,10,10,10,-10,-10,7,3 이면 먼저 a에 있는 각 숫자들의 개수를 딕셔너리로 저정한다.

a_dict = {6: 1, 3: 2, 2: 1, 10: 3, -10: 2, 7: 1}

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
M = int(input())
b = list(map(int, input().split()))

a_dict = {}
for num in a:               #a의 num이 a_dict 의 key 값이 되고 
    if num not in a_dict:   # a_dict 의 존재유무에 따라 value 값을 저장  
        a_dict[num] = 1     # a_dict {}에 없을시 1
    else:
        a_dict[num] += 1    # a_dict {}에 있을시 +1

result = []
for num in b:               # a_dict = {6: 1, 3: 2, 2: 1, 10: 3, -10: 2, 7: 1}
    if num in a_dict:       # a_dict 에서 b 10 9 -5 2 3 4 5 -10 값에 따른 a_dict value 값을 반환
        result.append(a_dict[num])
    else:
        result.append(0)

print(' '.join(map(str, result)))