문제

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.
두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

코드

import sys
input = sys.stdin.readline

tc = int(input())
for i in range(tc):
    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)
    aIdx = 0
    bIdx = 0
    cnt = 0
    while aIdx < n and bIdx < m:
        if A[aIdx] > B[bIdx]:
            cnt += m - bIdx
            aIdx += 1
        else:
            bIdx += 1
    print(cnt)

설명

투 포인터를 이용해서 문제를 풀었다. 두 집합 A, B를 내림차순으로 정렬하고 첫 번째 원소부터 A[aIdx]번째 원소가 B[Idx]번째보다 크다면 B[Idx]번째 이후에 있는 모든 원소보다 크기 때문에 그 개수를 cnt에 저장하고 A의 인덱스를 하나 증가시킨다. 그렇지 않다면 B의 인덱스를 하나 증가시키며 반복문이 종료되었을 때 cnt를 출력시켰다.