백준 7795번(Python) : 먹을 것인가 먹힐 것인가

www.acmicpc.net/problem/7795

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

 

단순하게 반복문을 통해 두 리스트를 비교하면 시간 초과가 생겨서 문제를 풀지 못한다. 따라서 이분 탐색을 활용하여 문제를 풀어야 한다. 이분 탐색을 하기전, 정렬을 한 뒤 이분탐색에 의하여 도출한 인덱스를 이용하여 답을 구하면 된다. 어차피 이분탐색에 의해 도출된 인덱스보다 작은 부분은 문제의 조건을 만족할 것이기에 따로 신경을 쓰지 않아도 된다.

 

import sys
input = sys.stdin.readline

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())
    n_arr = list(map(int, input().split()))
    m_arr = list(map(int, input().split()))
    count = 0
    n_arr.sort()
    m_arr.sort()

    for i in n_arr:
        count += binary_search(i,m_arr) + 1

    print(count)