백준 7795 : 먹을 것인가 먹힐 것인가 [JAVA]

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

 

[난이도]

- Silver 3

 

[알고리즘]

- 이분탐색

 

[코드]

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

public class Main {
    static int T, N, M, answer;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            answer = 0;
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            arr = new int[N];
            M = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr);

            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                int key = Integer.parseInt(st.nextToken());
                answer += binarySearch(key);
            }

            System.out.println(answer);
        }

    }
    static int binarySearch(int key) {
        int left = 0;
        int right = N - 1;
        while (left <= right) { // left가 right를 넘어서기 전까지 반복
            int mid = (left + right) / 2;
            if (key >= arr[mid]) { // key가 mid 와 같거나 클 경우
                left = mid + 1;
            } else if (key < arr[mid]) { // key가 mid 보다 작을 경우
                right = mid - 1;
            }
        }
        // left가 right를 넘어감
        return N - right - 1; 
    }
}

[풀이]

for문을 적게 사용하고 싶어서 B를기준으로 이분탐색을 했다. A가 B를 먹을 수 있는 쌍을 구하는게 아닌 B가 A에게 먹힐 수 있는 쌍을 구했다.