백준 알고리즘 7795번 먹을 것인가 먹힐 것인가(python)

단순하게 A랑 B를 비교하면서 개수를 새면 시간 초과가 나와서 이분 탐색을 사용했다.

이분 탐색을 사용해 B에서 A의 한 요소(a) 보다 작은 수들 중에 제일 큰 수의 위치(인덱스)를 찾는 것이 핵심이다.

EX) A = [2, 7, 13], B = [11, 103, 215, 290] 일 때

cnt = 0

A[0] = 2 -> B에는 2보다 작은 수가 없음 -> res = -1 -> cnt += (-1 + 1) -> cnt = 0

A[1] = 7 -> B에는 7보다 작은 수가 없음 -> res = -1 -> cnt += (-1 + 1) -> cnt = 0

A[2] = 13 -> B에서 13보다 작은 수는 2 인덱스는 0 -> res = 0 -> cnt += (0 + 1) -> cnt = 1

결과: 1

def binary_search(li, a):
    s, e = 0, len(li)-1
    res = -1
    while s <= e:
        m = (s + e) // 2
        if li[m] < a:
            res = m
            s = m + 1
        else:
            e = m - 1
    return res
    
    
for _ in range(int(input())):
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    cnt = 0
    for a in A:
        cnt += (binary_search(B, a) + 1)
    print(cnt)

 

bisect 라이브러리를 활용하면 훨씬 짧고 빠르게 해결할 수 있다.

import bisect

for _ in range(int(input())):
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    cnt = 0
    for a in A:
        cnt += (bisect.bisect(B, a-1))
    print(cnt)