간단한 두 포인터 문제를 풀어보자.

BOJ 7795 - 먹을 것인가 먹힐 것인가 링크
(2022.10.05 기준 S3)
(치팅하지 마세요)

문제

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍의 개수 출력

알고리즘

두 생명체의 크기들을 오름차순으로 정렬하면 A를 가르키는 포인터는 전에 가르켰던 포인터의 쌍을 전부 포함하게 된다. 이유는 풀이에서 후술.

풀이

문제 예제의 첫번째 테스트 케이스를 살펴보자.
A와 B를 정렬하면 밑 그림처럼 된다.

여기서 가능한 쌍을 이어보면

이렇게 된다. 뭔가 보이지 않는가?

이렇게 정렬하여 나타내어 보면 한 가지 사실을 알 수 있다.
앞에서 묶을 수 있었던 B의 원소는 앞으로도 쭉 쌍으로 묶일 수 있다.
A보다 작은 모든 B는 쌍으로 묶이기 때문에, A가 커져도 앞에서 묶였던 B는 그대로 계속 쌍으로 묶이는 것이다.

이를 두 포인터로 나타낼 수 있다.
A의 포인터보다 B의 포인터가 작은 동안 B의 포인터를 옮기고 포인터의 위치만큼 답에 더하고, A의 포인터를 1씩 옮기면서 반복하면 되는 것이다.

코드

import sys; input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    # A와 B 둘 다 정렬
    A = sorted(map(int, input().split()))
    B = sorted(map(int, input().split()))
    # i는 A를 가르키는 포인터, j는 B를 가르키는 포인터.
    # A[i] > B[j]인 동안 포인터를 옮기고
    # 포인터의 위치만큼 결과에 더해주면 된다.
    j = result = 0
    for i in range(N):
        while j < M: # 범위 안이어야 한다.
            if A[i] > B[j]:
                j += 1
            else:
                break
        result += j
    print(result)

for _ in range(int(input())):
    solve()

여담

두 배열을 이용하는 간단한 두 포인터 문제였다.