2022.02.02 40일차

백준 7795번 (먹을 것인가 먹힐 것인가)

문제

심해에는 두 종류의 생명체 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보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

나의 풀이

1. 테스트 개수 T, A의 수 N, B의 수 M, N의 배열 nArr, M의 배열 mArr(정렬)
2. nArr 반복문 사용, 반복문 내에서 이분 탐색(기준: mArr 인덱스)
3. 최소값(min): 0, 최대값(max): M - 1, count: 0, 더하는 기준(num): 0
4. while문 사용(min <= max)
5. nArr에 있는 값이 mArr[mid]보다 크면
   num = mid + 1(기준 이하의 값 모두 카운트에 포함하도록 num 활용)
   min = mid + 1
6. nArr에 있는 값이 mArr[mid]보다 작거나 같으면
   max = mid - 1
7. count += num, count 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

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

        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int[] nArr = new int[N];

            for (int i = 0; i < N; i++) {
                nArr[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            int[] mArr = new int[M];

            for (int x = 0; x < M; x++) {
                mArr[x] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(mArr);

            int count = 0;

            for (int k = 0; k < N; k++) {
                int min = 0;
                int max = M - 1;
                int num = 0;

                while(min <= max) {
                    int mid = (min + max) / 2;

                    if (nArr[k] > mArr[mid]) {
                        num = mid + 1;
                        min = mid + 1;
                    } else {
                        max = mid - 1;
                    }
                }
                count += num;
            }

            System.out.println(count);
        }

    }
}