[알고리즘] 이분탐색 강의 풀이 - 백준 7795

1. 문제

https://www.acmicpc.net/problem/7795
심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000)

3. 풀이

1. 문제 파악하기

• 정답의 최대치

모든 쌍이 정답인 경우 : N*M = 4억 -> Integer 범위 안

2. 접근

• 해야할 일
  B에서 A[i] 미만인 원소 찾기
  A[i]를 볼 때 마다 B에서 O(M)의 시간동안 탐색
  -> 전체 A에 대해 NM의 시간 발생
  -> O(NM)
  -> 시간초과 발생

• B에서 A[i] 미만인 원소 탐색을 빨리 끝내야 함
  -> 이분탐색 이용 (O(logM)
  -> 전체 A에 대해 O(NlogM)의 시간 발생

3. 시간, 공간 복잡도 계산

1. B 배열 정렬 -> O(MlogM)
2. 모든 A의 원소마다 B 배열에 대해 이분 탐색 -> O(NlogM)
3. 총 시간 복잡도 : O((N+M)logM)

4. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class eat_7795 {

    static int a,b;
    static int[] arr_a;
    static int[] arr_b;

    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int tc = Integer.parseInt(bf.readLine());

        for(int i=0;i<tc;i++){
            st = new StringTokenizer(bf.readLine()," ");
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            arr_a = new int[a];
            arr_b = new int[b];

            st = new StringTokenizer(bf.readLine()," ");
            for(int j=0;j<a;j++){
                arr_a[j] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(bf.readLine()," ");
            for(int k=0;k<b;k++){
                arr_b[k] = Integer.parseInt(st.nextToken());
            }

            //B 정렬
            Arrays.sort(arr_b);
            int answer = 0;

            //A[l]보다 작은 B 원소가 몇개 있는지 count;
            for(int l=0;l<a;l++){
                answer += binary_search(0,b-1,arr_a[l]);
            }

            System.out.println(answer);

        }



    }

    //A[L....R]에서 X미만의 수(x보다 작은수) 중 가장 오른쪽 인덱스 return
    //없으면 L-1을 return(갱신된게 없으면 자기 자신 return)
    public static int binary_search(int L, int R, int X){
        int result = L;
        while(L<=R){
            int mid = (L + R)/2;

            //현재 A값보다 작으면
            if(arr_b[mid]<X){
                //인덱스 위치+1이 개수
                result = mid+1;

                //왼쪽 인덱스를 갱신
                L = mid+1;
            }
            //현재 A값보다 크면 가치 없음
            //오른쪽 구간버리고 오른쪽 인덱스 갱신
            else if(arr_b[mid]>=X){
                R = mid-1;
            }
        }

        return result;
    }

}