[백준/python] 7795 먹을것인가 먹힐 것인가

이 문제는 구현은 쉽지만 그냥 for문으로 돌리면 시간초과가 난다 ㅠ 그래서 더 빨리 해결할 수 있는 알고리즘을 찾아야 한다. 빨리 해결하는 방법은 그리 어렵지 않다.

일단 sort를 이용해서 두 수열(A,B)을 내림차순으로 정렬시킨다.

이 때 A의 값을 하나씩 늘리면서 점검하고, B도 값을 늘리면서 점검하는데 만약 B의 어떤 값이 A보다 작은게 나오면 어차피 뒤에 있는 것들도 다 작을 것이므로 그냥 뒤에 있는 것들의 개수를 더해주고(len(B)-j) 다시 A로 패스시킨다. 

사실상 A -> A'로 넘어갈 때 어차피 A'은 A보다 작으니까 A가 B에서 그냥 stop해줬던 부분(A가 자기보다 작아서 그냥 pass했던)부터 다시 점검해주면 되니까 B의 앞에 것들은(A가 봤을 때 자기보다 컸으므로 A'에게도 큰 것들이 되므로) 필요가 없게 된다.

 

import sys
input=sys.stdin.readline


t=int(input())
for i in range(t):
    sum=0
    N,M=map(int, input().split())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    A.sort(reverse=True)
    B.sort(reverse=True)
    a=0
    b=0
    n=len(A)
    m=len(B)
    while a < n and b < m:
        if A[a] > B[b]:
            sum += m - b
            a += 1
        else:
            b += 1
        
    print(sum)