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

문제

심해에는 두 종류의 생명체 A와 B가 존재하며, A는 B를 먹습니다. A는 자기보다 크기가 작은 먹이만 먹을 수 있습니다. 두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개인지 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 테스트 케이스의 개수 T가 주어집니다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어집니다. 둘째 줄에는 A의 크기가, 셋째 줄에는 B의 크기가 주어집니다.
• 출력: 각 테스트 케이스마다 A가 B보다 큰 쌍의 개수를 출력합니다.

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

풀이: 우선순위 큐(Priority Queue)와 정렬을 활용한 탐색

A와 B의 크기를 비교하여 A > B인 경우의 수를 효율적으로 구하는 방식입니다. 이중 반복문으로 모두 단순 비교하면 시간 초과가 발생할 수 있으므로, 정렬과 우선순위 큐를 활용하여 탐색 시간을 크게 단축합니다.

• 데이터 저장 및 정렬: A 배열의 원소는 우선순위 큐(Min-Heap)에 삽입하여 항상 최솟값부터 확인할 수 있도록 구성합니다. B 배열은 일반 배열에 입력받은 뒤 오름차순으로 정렬합니다.
• 조건 기반 큐 필터링: 정렬된 B 배열의 원소를 가장 작은 것부터 차례대로 순회합니다. 우선순위 큐의 최상단 원소(pq.peek())가 현재 탐색 중인 B의 원소보다 작거나 같다면, 해당 A는 현재의 B뿐만 아니라 이후에 등장할 더 큰 B들도 절대 먹을 수 없습니다. 따라서 poll()을 호출하여 큐에서 완전히 제거합니다.
• 정답 누적: 반복문을 통해 현재 B보다 작거나 같은 A들을 모두 제거하고 나면, 큐에 남아있는 원소들은 모두 현재 B보다 크기가 큰 A들입니다. 즉, 현재 B를 먹을 수 있는 A의 개수는 남아있는 큐의 크기(pq.size())와 일치하므로 이를 정답 변수(ans)에 누적합니다.
• 효율성 보장: B 배열이 오름차순으로 정렬되어 있기 때문에, 한 번 큐에서 제거된 A는 다음 B에 대해서 다시 검사할 필요가 없습니다. 탐색 과정에서 A의 원소들은 우선순위 큐에서 최대 한 번씩만 빠져나오게 되므로, 불필요한 중복 연산 없이 효율적으로 정답을 구할 수 있습니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int t = Integer.parseInt(br.readLine());

       while (t-- > 0) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int n = Integer.parseInt(st.nextToken());
          int m = Integer.parseInt(st.nextToken());

          PriorityQueue<Integer> pq = new PriorityQueue<>();
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < n; i++) {
             pq.add(Integer.parseInt(st.nextToken()));
          }

          int[] b = new int[m];
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < m; i++) {
             b[i] = Integer.parseInt(st.nextToken());
          }

          Arrays.sort(b);

          int ans = 0;

          for (int i = 0; i < m; i++) {
             while (!pq.isEmpty() && pq.peek() <= b[i]) {
                pq.poll();
             }
             ans += pq.size();
          }

          bw.write(ans + "\n");
       }

       bw.flush();
    }
}

알고리즘 분류

정렬 (Sorting), 두 포인터 (Two Pointers)