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

https://www.acmicpc.net/problem/7795

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

 

문제 해결

• 모든 원소를 1대1로 비교해서 계산하는 것은 너무 비효율적이라는 생각이 든다.
• 정렬을 이용해서 A와 B를 오름차순으로 정렬하고, $i \in {0,1,2,3, . . .n-1} $ $j \in {0,1,2,3, .. m-1}$ 인 임의의 $i, j$에 대해서 A[i] > B[j]이면 A[i+1] > B[j]임을 생각을 하면 좋다.
• 만약 A[i]>B[j-1], A[i] ≤ B[j]이고 A[i+1] ≤ B[j] 이면 A[i+1]이 먹을 수 있는 것은 j개라는 것을 알 수 있다.
• 이를 고려하면 쉽게 해결할 수 있다.

 

CODE

import sys
input = sys.stdin.readline



t = int(input())
for _ in range(t):
    n,m = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int,input().split()))
    A.sort()
    B.sort()
    answer = 0
    j = 0
    for i in range(n):
        while j<m:
            if A[i] > B[j]:
                j += 1
            else:
                answer += j
                break
        else:
            answer += m
    print(answer)