백준 7795번 - 먹을 것인가 먹힐 것인가 [Java]

이 문제를 브루트포스로 풀게 된다면 N과 M이 20000인 경우에 20000*20000이라 대략 4억번의 연산 횟수가 시행될 것이고 

보통 1초당 약 연산횟수가 1억회라고 생각 하기때문에 시간 제한이 1초인 이 문제를 틀리게 될 가능성이 높다.

 

따라서 이분탐색으로 문제를 풀어보자

 

 

우선 A와 B를 배열로 입력받고

B를 정렬한뒤

A값을 토대로 B를 이분탐색 한다.

 

 

따라서 이분탐색으로 문제를 풀면

B를 정렬하는 시간복잡도가 O(M logM) 이고 이분탐색이 O(logM)이며 이분탐색을 A의 크기인 N만큼 시행할것이니

대략 O(n log n)의 복잡도를 가질것이다.

 

 

정렬된 B를 A값으로 이분 탐색이 끝나면

인덱스를 기준으로 왼쪽이 항상 A보다 작은 B의 값이므로

인덱스 값이 선택된 A의 값보다 작은 B의 수이다.

 

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();

        for (int i = 0; i < testCase; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            Integer[] a = new Integer[n];
            Integer[] b = new Integer[m];

            for (int x = 0; x < n; x++) a[x] = sc.nextInt();
            for (int x = 0; x < m; x++) b[x] = sc.nextInt();
            Arrays.sort(b);



            int result = 0;


            for (int x = 0; x < n; x++) {
                int first = 0;
                int end = m - 1;
                int index = 0;
                int mid = (end + first) / 2;
                while (first <= end) {
                    mid = (end + first) / 2;
                    if (a[x] > b[mid]) {
                        first = mid+1;
                        index = mid+1;
                    }
                    else {
                        end = mid -1;
                    }
                }
                result += index;
            }
            System.out.println(result);
        }
        sc.close();
    }


}

 

index 변수를 따로 0으로 초기화 해주고 A값이 현재의 B값보다 클 때마다 값을 갱신해주고

그외의 경우는 index에 값을 넣지 않으면 구현이 가능하다.