자바(백준) - 7795 먹을 것인가 먹힐 것인가

오답 노트 & 새로 알게 된 점

위 문제는 이분 탐색으로 lowerbound를 구하는 문제이다.

 

B의 숫자 중에 A의 숫자보다 작은 것들을 구하면 된다.

 

시간 복잡도는

B를 정렬해야하므로 MlogM

B에서 이분 탐색을 실시할 때 logM, 이와 같은 연산을 A의 개수만큼 즉 N만큼 해야하므로 NlogM

둘을 더하면 (N+M)logM

 

---

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, M;
    static int A[], B[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int test_case = atoi(br.readLine());
 
        for (int test = 0; test < test_case; test++) {
 
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            N = atoi(st.nextToken());
            M = atoi(st.nextToken());
 
            A = new int[N];
            B = new int[M];
 
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                A[i] = atoi(st.nextToken());
            }
 
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < M; i++) {
                B[i] = atoi(st.nextToken());
            }
 
            Arrays.sort(B);
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                cnt += binarySearch(A[i]);
            }
            System.out.println(cnt);
        }
    }
 
    static int binarySearch(int target) {
        int s = 0, e = M-1, mid = 0, rel = M;
 
        while (s <= e) {
            mid = (s + e) / 2;
 
            if (B[mid] < target) {
                rel = mid;
                s = mid + 1;
            }
            else{
                e = mid - 1;
            }
        }
 
        if(rel == M) return 0;
        return rel + 1;
    }
}