방구석프로의 이야기

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

문제 해결을 위한 과정

이 문제의 경우 일반적인 이중 for문을 사용하여 문제를 해결하면 최악의 경우 N^2으로 20,000 * 20,000 즉 4억 번 연산을 해야 하므로 시간초과를 받게 됩니다. 따라서 두 배열을 내림차순 정렬한 뒤 A배열의 값, B배열을 비교하면 됩니다. 이렇게 하게 되면 매번 비교할 필요 없이 A 배열값 보다 항상 작은 B배열의 개수를 구할 수 있습니다.

소스코드

T = int(input())
for t in range(T):
  n, m = map(int, input().split())
  arr1 = list(map(int, input().split()))
  arr2 = list(map(int, input().split()))
  arr1.sort(reverse = True)
  arr2.sort(reverse = True)
  idx = 0
  ans = 0
  for i in range(len(arr1)):
    while idx < len(arr2):
      if arr1[i] > arr2[idx]:
        ans += len(arr2) - idx
        break
      else:
        idx += 1
  print(ans)