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

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

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

 

 

아이디어

A 원소의 크기가 B의 원소보다 작은 쌍을 구해야 한다.

 

먼저 순차 탐색을 생각해봤다.

A의 모든 원소마다 B의 모든 원소를 비교하면 (1 ≤ N, M ≤ 20,000)이므로 시간 복잡도가 O(N^2) 즉, O(4*10^8) 이므로 1초 내에 풀 수 없다.

 

탐색 시간을 줄이기 위해 이분탐색을 이용한다.

B를 정렬 후 A 원소들을 기준으로 이분탐색을 하여 구한다. B를 정렬할 때 O(N log N) 이분 탐색할 때 O(N log N)이므로 시간 안에 빠르게 찾아낼 수 있다.

 

구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int T, N, M, ans;
    static int[] A, B;

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        StringTokenizer st;
        for (int t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            ans = 0;

            A = new int[N + 1];
            B = new int[M + 1];

            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= N; i++) {
                A[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= M; i++) {
                B[i] = Integer.parseInt(st.nextToken());
            }

            pro();

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

    }

    static void pro() throws IOException {
        // B 정렬
        Arrays.sort(B, 1, M + 1);

        for (int i = 1; i <= N; i++) {
            // 이분탐색 진행
            ans += bsearch(1, M, A[i]);
        }

    }

    private static int bsearch(int L, int R, int X) {

        // A에서 X보다 작은 수 중 제일 오른쪽 인덱스를 return
        // 그게 없다면 L-1 return

        int result = L - 1;

        while (L <= R) {
            int mid = (L + R) / 2;

            if (B[mid] >= X) {
                R = mid - 1;
            } else if (B[mid] < X) {
                result = mid;
                L = mid + 1;
            }
        }

        return result;
    }

    public static void main(String[] args) throws IOException {
        init();

        bw.close();
    }

}