백준 숫자 카드 2 PYTHON

 

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

 

import bisect
import sys
input = sys.stdin.readline
a = int(input())
check = list(map(int, input().split()))
check.sort()
b = int(input())
find = list(map(int, input().split()))
count = []
for num in find:
    left_index = bisect.bisect_left(check, num)
    right_index = bisect.bisect_right(check, num)
    count.append(right_index - left_index)
for i in range(len(count)):
    print(count[i],end=' ')

 

원래는 for문과 count를 사용하여 문제를 풀려했다. 하지만 시간초과가 나올껏같아, 이진탐색을 사용하여 문제를 해결했다.

파이썬 bisect를 사용하면 이진탐색을 구현하지않고 사용할수있다. 위의 문제에서 살짝 배운점은 갯수를 어떻게 셀것이었다.

어떤수를 탐색한뒤,left,right의 인덱스를 기준을 잡고 개수를 세어주면 빠지는 개수없이 전부 셀수 있다.