[백준/파이썬] #7795 먹을 것인가 먹힐 것인가

문제

---

7795번: 먹을 것인가 먹힐 것인가 (acmicpc.net)

7795번: 먹을 것인가 먹힐 것인가

---

문제설명

---

 

이 문제 풀이에 대해 시간 초과 오류 계속 발생하는데 

이를 해결하기 위한 방법은 바로 '이분 탐색' 이다.

생명체 A의 각 요소와 생명체 B의 각 요소를 비교해

A의 요소 값 > B의 요소 값을 구하는 과정을 가진다.

이를 위해 생명체 A와 B를 각각 리스트로 표현한다.

A[i] 와 B[0] ~ B[i]의 크기 비교를 

리스트 A의 크기인 N번 반복해야한다.

이를 위해 정렬한 리스트 B에 대해 시작점(= start)과 끝점(= end)을

기준으로 중간 지점인 B[mid]와 A[i] (= target) 간의 비교를 통해 

시작점과 끝점의 범위를 수정한다. 이는 start > end 일 때 종료한다.

 

---

코드

---

def binary_search(target, data):
    start = 0
    end = len(data) - 1
    res = -1
    while (start <= end) :
        mid = (start + end ) // 2
        if data[mid] < target:
             res  = mid
            start = mid + 1
        else:
            end  = mid - 1
    return  res 

test_case = int(input())
for _ in range(test_case):
    n, m = map(int, input().split())
    A_arr = list(map(int, input().split()))
    B_arr = list(map(int, input().split()))

    count = 0
    A_arr.sort()
    B_arr.sort()

    for i in A_arr:
        count += binary_search(i, B_arr) + 1

  print(count)

 

---