[백준] 7795 먹을 것인가 먹힐 것인가 - 이분탐색(binary search) JAVA

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

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

코드설명

이분탐색 문제입니다.

 

이분탐색의 시간복잡도는 O(log N)이므로 T, N, M을 고려하였을때 이번 문제에서는 O(T N log M) 입니다.

 

문제 조건을 보면, (1 ≤ N, M ≤ 20,000)  이므로 만약 M을 단순히 순회해서 찾아내는 경우 최악의 경우 20,000 ^ 2 * T 이기에 시간초과가 날 수 있습니다. T의 범위가 주어져있지는 않아서 조금 애매할 수 있습니다.

 

 

문제의 기본로직은 N의 원소가  M의 배열을 이분탐색하여 N의 원소를 찾아냅니다. 해당 위치의 인덱스가 곧 N보다 작거나 같은 것의 개수이므로 answer += 1 처리를 하며 진행합니다.

 

또한 이 문제에서 아래의 코드처럼 target > brr[middle] 일떄 start = middle + 1 처리하는 이유는 while(start <= end) 처리하였기에 target과 brr[middle]이 같아질때 end를 줄여주면서 처리해야만 반복문이 끝나기에 아래처럼 처리했습니다.

if(target > brr[middle]) {
    start = middle + 1;
}else {
    end = middle - 1;
}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int T;
	public static int N, M;
	public static int[] arr, brr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	T = Integer.parseInt(st.nextToken());
    	for(int t=0;t<T;t++) {
        	st = new StringTokenizer(br.readLine());
       	 	N = Integer.parseInt(st.nextToken());
       	 	M = Integer.parseInt(st.nextToken());
       	 	
       	 	arr = new int[N];
       	 	brr = new int[M];
       	 	
       	 	st = new StringTokenizer(br.readLine());
       	 	for(int i=0;i<N;i++) {
       	 		arr[i] = Integer.parseInt(st.nextToken());
       	 	}
       	 	
       	 	st = new StringTokenizer(br.readLine());
       	 	for(int i=0;i<M;i++) {
       	 		brr[i] = Integer.parseInt(st.nextToken());
       	 	}
       	 	Arrays.sort(brr);
       	 	
    		answer = 0;
       	 	for(int i=0;i<N;i++) {
       	 		binarySearch(arr[i]);
       	 	}
       	 	System.out.println(answer);
       	 	
    	}


    }
    
    public static void binarySearch(int target) {
    	int start = 0;
    	int end = M-1;
    	int middle = 0;
    	while(start <= end) {
    		middle = ( start + end ) / 2;
    		
    		if(target > brr[middle]) {
    			start = middle + 1;
    		}else {
    			end = middle - 1;
    		}
    		
    	}
    	
//    	System.out.println(start);
    	answer += start;
    }
    
}

 

package Main;

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

public class Main {
    public static int N, T, M; 
    public static int answer = 0;
    public static int[] A, B;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			A = new int[N]; B = new int[M];
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<N; i++) {
				A[i] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<M;i++) {
				B[i] = Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(B);
			answer = 0;
			for(int i=0;i<N;i++) {
				answer += binarySearch(0, M - 1, A[i]);
			}
			System.out.println(answer);
		}
		
	}
    
    public static int binarySearch(int lo, int hi, int target) {
    	int left = lo - 1;
    	int right = hi + 1;
    	
    	while(left + 1 < right) {
    		int mid = (left + right) / 2;
    		
    		if(target > B[mid]) {
    			left = mid;
    		} else if(target <= B[mid]) {
    			right = mid;
    		}
    		
    	}
    	return right;
    }
    
    
}