이번 문제는 이분 탐색을 통해 해결하였다. 우선 A와 B를 입력받음과 동시에 오름차순으로 정렬시켜놓고, A를 순회하며 B에 대한 A[i]의 이분 탐색을 통해 A[i]보다 작은 수의 갯수를 도출해낸다. 이때, 무의미한 탐색을 줄이기 위해 A[i]가 B의 첫번째 원소보다 작거나 같을 경우에는 탐색하지 않고 넘어가도록 하였다.

• binary_search함수를 left, right, target을 인자로 갖도록 선언한다.
  -> target보다 작은 수의 갯수를 저장할 변수 result를 0으로 선언한다.
  -> left가 right 이하일 동안 반복하는 while문을 돌린다.
  --> mid를 (left+right)//2로 갱신한다.
  --> 만약 B[mid]가 target보다 작을 경우,
  ---> left를 mid+1로 갱신한다.
  ---> result를 mid로 갱신한다.
  --> 그 외의 경우,
  ---> right를 mid-1로 갱신한다.
  -> result+1을 반환한다.
• t를 입력받는다.
• t번 반복하는 for문을 돌린다.
  -> a, b를 입력받는다.
  -> A 리스트를 입력받아 정렬된 순서로 저장한다.
  -> B 리스트를 입력받아 정렬된 순서로 저장한다.
  -> 정답을 저장할 변수 answer를 0으로 선언한다.
  -> A를 순회하는 i에 대한 for문을 돌린다.
  --> 만약 i가 B[0]보다 작거나 같을 경우, 다음 반복으로 넘어간다.
  --> left, right를 0, b-1로 선언한다.
  --> answer에 binary_search(left, right, i)의 반환값을 더한다.
  -> answer를 출력한다.

Code

def binary_search(left, right, target):
    result=0
    while left<=right:
        mid=(left+right)//2
        if B[mid]<target:
            left=mid+1
            result=mid
        else:
            right=mid-1
    return result+1

t=int(input())
for _ in range(t):
    a, b=map(int, input().split())
    A=sorted(list(map(int, input().split())))
    B=sorted(list(map(int, input().split())))
    answer=0
    for i in A:
        if i<=B[0]:
            continue
        left, right=0, b-1
        answer+=binary_search(left, right, i)
    print(answer)