[백준] 10816번 숫자 카드, Python

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

이분 탐색을 사용하는 문제라고 생각이 들어 반복문을 사용해 이분 탐색을 했지만...시간 초과가 나버렸다.

import sys
n=int(sys.stdin.readline())
array=list(map(int,sys.stdin.readline().split()))
m=int(input())
nums=list(map(int,sys.stdin.readline().split()))
array.sort()
start=0
end=n-1
result=[]
def binary_search(array,x,start,end):
  cnt=0
  while(start<=end):
    array.sort()
    mid=(start+end)//2
    if array[mid]==x:
      cnt+=1
      array[mid]=10000001 
    elif array[mid]>x:
      end=mid-1
    else:
      start=mid+1
  return cnt

for x in nums:
  a=binary_search(array,x,start,end)
  result.append(a)
for i in result:
  print(i,end=" ")

위 코드가 시간 초과가 난 코드다. while문을 써서 시간 초과가 난 것인데 정확히 왜인지는 잘 모르겠다. 하여튼 이코테에서 배운 bisect 라이브러리를 활용해 풀어보니 정상적으로 작동했다.

import sys
from bisect import bisect_left,bisect_right
n=int(sys.stdin.readline())
array=list(map(int,sys.stdin.readline().split()))
m=int(input())
nums=list(map(int,sys.stdin.readline().split()))
array.sort()
result=[]

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

for i in nums:
  print(count_by_range(array,i,i),end=" ")

bisect를 활용해 정렬된 데이터에서 찾고자 하는 데이터의 가장 오른쪽 인덱스와 가장 왼쪽 인덱스를 빼서 개수를 구할 수 있었다.