[7795] 먹을 것인가 먹힐 것인가

🔗 문제 링크

https://www.acmicpc.net/problem/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보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

⚠️ 제한사항

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다.

• 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)

---

🗝 풀이 (언어 : Java)

하나하나 확인하면 이중 반복문으로 시간복잡도 $O(N*M)$으로 시간초과 판정이 난다. B를 정렬한 후에, A의 원소별로 B를 조회할 때 이분 탐색을 사용하면 반복문 한번과 함께 $O((N+M)logM)$의 시간복잡도로 풀 수가 있다. 왼쪽과 오른쪽 경계를 양끝으로 정해주고 임의의 인덱스부터 시작해서, 더 크면 왼쪽 경계값을 키우고, 더 작으면 오른쪽 경계값을 줄인다. 이 과정을 반복하다 왼쪽 경계값이 오른쪽 경계값보다 커지게 되면 목표 숫자와 가장 근접한 숫자의 인덱스를 찾게된다. 정렬된 배열이므로 인덱스만 알면 앞에 몇개의 숫자가 있는지 알 수 있다.

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private int eatOrEaten(int[][] arr) {
        int[] manyA = arr[0], manyB = arr[1];
        int answer = 0, lenA = manyA.length, lenB = manyB.length;
        // b를 정렬
        Arrays.sort(manyB);
        // 이분탐색 시행
        for (int i = 0; i < lenA; i++) {
            int left = 0, right = lenB - 1, idx = 0;
            // 왼쪽 경계가 오른쪽 경계보다 커지면 종료
            while (left <= right) {
                idx = (left + right) / 2;
                // 현재 위치의 B의 값이 A의 값보다 작은 경우, 왼쪽 경계 갱신
                if (manyA[i] > manyB[idx])
                    left = idx + 1;
                    // 현재 위치의 B의 값이 A의 값보다 크거나 같은 경우, 오른쪽 경계 갱신
                else
                    right = idx - 1;
            }
            // 타겟 숫자와 가장 근접한 B의 인덱스 숫자가 타겟 숫자보다 작으면 그 수도 카운트해준다
            answer += (manyA[i] > manyB[idx]) ? idx + 1 : idx;
        }
        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main main = new Main();
        int n = sc.nextInt();
        int[][] arr = new int[2][];
        for (int i = 0; i < n; i++) {
            int numA = sc.nextInt(), numB = sc.nextInt();
            int[] manyA = new int[numA], manyB = new int[numB];
            for (int j = 0; j < numA; j++)
                manyA[j] = sc.nextInt();
            for (int k = 0; k < numB; k++)
                manyB[k] = sc.nextInt();
            arr[0] = manyA;
            arr[1] = manyB;
            System.out.println(main.eatOrEaten(arr));
        }
        sc.close();
    }
}