백준(10816) - 숫자 카드2 Python

백준(10816) - 숫자 카드2

문제풀이: 해쉬, 파이썬

해결방법

예시)

# 입력 #
10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

# 출력결과 #
3 0 0 1 2 0 0 2

• 백준 사이트에서는 백준(10815) - 숫자 카드 와 마찬가지로 이분탐색 문제로 분류되어 있지만 해쉬 알고리즘으로 푸는 방식이 시간 효율이 좋다.
• 파이썬 dict를 사용하면 쉽게 해결이 가능하다.

input()
N = map(int,input().split())
input()
M = map(int,input().split())
hashmap = {}
for n in N:
    if n in hashmap:
        hashmap[n] += 1
    else:
        hashmap[n] = 1

print(' '.join(str(hashmap[m]) if m in hashmap else '0' for m in M))

이진탐색 사용

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

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

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

cards.sort()
for d in data:
    a = bisect_left(cards, d)
    b = bisect_right(cards, d)
    print(b-a, end=" ")