자바 백준 7795번 문제 - 먹을 것인가 먹힐 것인가

문제 출처 : https://www.acmicpc.net/problem/7795

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

 

문제 :

 

 

풀이 :

T만큼 반복하는 반복문 안에서 N, M과 각 배열 입력받는다.

그리고 각 케이스마다 정답 리턴하는 함수 작성하고 사용한다.

arrA, arrB 정렬한 다음 arrA 기준으로 for문 돌리고

그 안에서 이분 탐색 알고리즘 이용해 arrA[i]보다 작은 arrB 개수들 계산해서 구하고자 하는 값 리턴시킨다.

 

 

소스코드 :

import java.util.*;
class Main {
	public int solution(int n, int m, int[] arrA, int[] arrB) {
		int cnt = 0;
		Arrays.sort(arrA);
		Arrays.sort(arrB);
		for(int i=0; i<n; i++) {
			int lt = 0, rt = m-1, idx = 0;
			while (lt <= rt) {
				int mid = (lt + rt) / 2;
				if (arrA[i] > arrB[mid]) {
					lt = mid + 1;
					idx = mid + 1;
				}
				else rt = mid - 1;
			}
			cnt += idx;
		}
		return cnt;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i=0; i<t; i++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			int[] arrA = new int[n];
			int[] arrB = new int[m];
			for(int j=0; j<n; j++) {
				arrA[j] = sc.nextInt();
			}
			for(int k=0; k<m; k++) {
				arrB[k] = sc.nextInt();
			}
			System.out.println(T.solution(n, m, arrA, arrB));
		}
	}
}