[BOJ] 10816

문제

me

이분탐색으로 했더니 시간 초과가 났다.
해쉬맵 형태로 하였다.

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

res={}
for num in search_nums:
    res[num]=0
left=0
right=n-1
for num in nums:
    if num in res:
        res[num]+=1

for num in search_nums:
    print(res[num],end=' ')

solution

출처
1. bisect

bisect는 파이썬에 내장되어있는 이진탐색 모듈인데
bisect_left(list, value)는 list에서 value가 들어갈 가장 왼쪽 인덱스,
bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 인덱스를 알려준다.

from bisect import bisect_left, bisect_right
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))
card.sort()

def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index


for i in range(len(test)):
    print(count_by_range(card, test[i], test[i]), end=' ')

2. 파이썬 내장 모듈인 Counter 이용

   Counter는 리스트를 값으로 주게 되면 해당 원소들이 몇 번 등장했는지 세어 딕셔너리 형태로 반환한다.

from collections import Counter
from sys import stdin

n = stdin.readline().rstrip()
card = list(map(int,stdin.readline().split()))
m = stdin.readline().rstrip()
test = list(map(int,stdin.readline().split()))

count = Counter(card)

for i in range(len(test)):
    if test[i] in count:
        print(count[test[i]], end=' ')
    else:
        print(0, end=' ')