[7795 먹을 것인가 먹힐 것인가]

• 문제 - www.acmicpc.net/problem/7795

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

 

• 분석 및 해결

쉽게 말해 A배열 모든 원소에 대해서 B배열에서 자신보다 작은 원소들의 개수의 합을 구하는 문제이다. 지난 번에 포스팅한 '순위 검색'에서의 이분 탐색을 적용해 해결했다.

 

• 소스 코드

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

public class BJ_7795 {

	private static int[] A, B;
	private static int T, N, M;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		T = Integer.parseInt(br.readLine());
		for(int iter = 0; iter < T; iter++) {
			StringTokenizer 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 index = 0; index < N; index++) {
				A[index] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine(), " ");
			for(int index = 0; index < M; index++) {
				B[index] = Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(B); // 이분 탐색을 위해 정렬 선처리
			System.out.println(solution());
		}
		
	}
	
	private static int solution() {
		int answer = 0;
		
		for(int index = 0; index < N; index++) {
			answer += binarySearch(A[index]);
		}
		
		return answer;
	}
	
	private static int binarySearch(int num) {
		int front = 0; // B배열의 첫 인덱스
		int back = M - 1; // B배열의 마지막 인덱스
		
		while(front <= back) {
			int midIndex = (front + back) / 2;
			
			if(num > B[midIndex]) {
				front = midIndex + 1;
			}
			else {
				back = midIndex - 1;
			}
		}
		
		return front; // 현재 인덱스가 자신보다 작은 원소들의 개수가 된다.
	}

}