백준 7795 - 먹을 것인가 먹힐 것인가

문제

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

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

 

 

풀이

A 배열에서 한 개씩 B 배열에 대해 탐색을 진행하면서 작은 값을 찾아야 한다. 이 때 2중 for문을 이용해서 A의 한 원소에 대해 B의 원소 전부를 탐색하면 시간초과가 발생한다. 따라서 B를 정렬 후 A 보다 작은 값의 개수를 이분 탐색으로 찾으면 된다. 일반적인 이분 탐색으로는 A 보다 작은 값의 개수를 찾을 수 없으므로 이분 탐색을 변형해 사용한다.

B 배열 중에서 A의 값보다 작은 값 중에 가장 큰 값의 인덱스를 반환하면 A의 값보다 작은 B의 원소 갯수를 알 수 있다.

 

 

코드

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

public class Main {

    static int N, M;
    static Scanner sc = new Scanner(System.in);
    static int[] A, B;

    public static void main(String[] args) {
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            input();
            solve();
        }
    }

    private static void solve() {
        Arrays.sort(B);
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            cnt += find(A[i]);
        }
        System.out.println(cnt);
    }

    private static int find(int x) {
        int l = 0, r = M - 1;
        int result = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (B[mid] < x) {
                result = mid + 1;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return result;
    }

    private static void input() {
        N = sc.nextInt();
        M = sc.nextInt();
        A = new int[N];
        B = new int[M];
        for (int i = 0; i < N; i++)
            A[i] = sc.nextInt();
        for (int i = 0; i < M; i++)
            B[i] = sc.nextInt();
    }
}