[백준] 7795번 먹을 것인가 먹힐 것인가 파이썬 코드

코드

import sys
input = sys.stdin.readline

def binary_search(arr, target, start, end):
  total = 0
  while start <= end:
    mid = (start + end) // 2
    if target > arr[mid]:
      total = mid + 1
      start = mid + 1
    else: end = mid - 1
  return total
      
a = int(input())
for _ in range(a):
  a, b = map(int, input().split())
  a_creature = list(map(int, input().split()))
  b_creature = sorted(list(map(int, input().split())))
  result = 0
  for i in a_creature:
    result += binary_search(b_creature, i, 0, b-1)
  print(result)

시간초과 코드

import sys
input = sys.stdin.readline

a = int(input())
def binary_search(arr, target, start, end):
  total = 0
  while start <= end:
    mid = (start + end) // 2
    if target > arr[mid]:
      total += len(arr[start:mid+1])
      start = mid + 1
    else: end = mid - 1
  return total
      

for _ in range(a):
  a, b = map(int, input().split())
  result = 0
  a_creature = list(map(int, input().split()))
  b_creature = sorted(list(map(int, input().split())))
  for i in a_creature:
    result += binary_search(b_creature, i, 0, b-1)
  print(result)

이분탐색 코드에 += 를 사용해 시간복잡도를 늘려버렸다... 그래서 이분탐색을 쓰는 의미가 퇴색된 듯. 아마 저번에 풀었던 문제들도 같은 원인을 가지고 있을 듯하다. 최대한 효율적으로 생각을 해보자.