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

백준 7795번 먹을 것인가 먹힐 것인가

백준 7795번은 풀이 방법에는 여러가지가 있겠지만 저는 이진탐색(Binary Search)를 활용했습니다. 처음에는 단순히 이진탐색으로 풀었는데 답이 틀렸다고 나왔습니다.
곰곰히 생각해보니까 중복이 여러개일때 문제가 발생했습니다. 그래서 중복을 고려했습니다. 타겟값을 찾고자 할때 단순히 찾았다고 끝이 나는것이 아니라 중복일때 그 타겟값이 시작한 부분을 찾고 싶었습니다. 그래서 lower bound의 개념을 활용했습니다.

이진탐색을 이용한 코드는 다음과 같습니다.

def lower_bounder(array, target, start, end):
    # 2 13 7
    # 11 103 215 290
    ans = -1
    if array[0] >= target:
        return 0
    if array[-1] < target:
        return len(array)
    while start <= end:
        mid = (start+end)//2
        if array[mid] < target:
            start = mid + 1
        elif array[mid] > target:
            end = mid - 1
        else:
            ans = mid
            end = mid - 1

    if ans != -1:
        return ans
    else:
        if array[mid] > target:
            return mid
        else:
            return mid+1

t = int(input())
result = 0
for i in range(t):
    a, b = map(int, input().split())
    a_array = [int(x) for x in input().split()]
    b_array = [int(x) for x in input().split()]

    b_array.sort()

    for el in a_array:
        result += lower_bounder(b_array, el, 0, len(b_array) - 1)
    print(result)
    result = 0