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

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

10816번: 숫자 카드 2

 

 

처음 in 함수를 사용한 방법으로 풀었는데 예제는 맞았지만 시간초과가 나왔다. 250,000,000,000가 걸리기 때문에 250초는 필요할 것이다. 정확하진 않지만 in 함수는 완전 탐색을 사용하는것 같다.

 

시간초과가 발생한 풀이)

n = int(input())
cards = list(map(int, input().split()))
m = int(input())
arr = list(map(int, input().split()))
answer = []
for cnt in arr:
    if cnt in cards:
        answer.append(cards.count(cnt))
    else:
        answer.append(0)
print(*answer)

 

해시를 이용한 풀이)

import sys
n = int(input())
card = list(map(int, sys.stdin.readline().split()))
m = int(input())
test = list(map(int, sys.stdin.readline().split()))

hash = {}

for i in card:
    if i in hash: #1
        hash[i] += 1
    else:
        hash[i] = 1

for i in test:
    if i in hash: #2
        print(hash[i], end=' ')
    else:
        print(0, end=' ')

 

사실 해시를 이용한 풀이(시간복잡도 O(n²))가 위의 풀이보다 코드도 이해하기 쉽고 훨씬 간단하다.

 

#1 : hash안에 card의 숫자가 있으면 key의 value +1, 없으면 새로추가해서 1로 지정

#2 : test의 숫자가 hash안에 있으면 key의 value 출력, 없으면 0 출력