[백준 7795] 먹을 것인가 먹힐 것인가 Java 풀이

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

 

접근

n이 최대 20,000, m이 최대 20,000이므로 선형 탐색을 사용한다면 최악의 경우 시간 복잡도가 O(n * m)가 될 것으로 예상됩니다. 따라서 이진 탐색을 사용하여 a가 b보다 큰 쌍의 개수를 구한다면 시간 복잡도를 O(m * logn)으로 줄일 수 있습니다.

 

코드

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

public class Main {
	static int n, m;
	static int[] a;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			// 입력 처리
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());

			a = new int[n];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				a[i] = Integer.parseInt(st.nextToken());
			}

			// 1. 배열 a를 오름차순으로 정렬한다.
			Arrays.sort(a);

			// 2. a가 b보다 큰 쌍의 개수를 구한다.
			st = new StringTokenizer(br.readLine());
			int ans = 0;
			for (int i = 0; i < m; i++) {
				int b = Integer.parseInt(st.nextToken());
				int count = getPairCount(b);
				ans += count;
			}
			sb.append(ans).append("\n");
		}

		// 결과 출력
		System.out.println(sb);
	}

	static int getPairCount(int b) {
		int s = 0;
		int e = n - 1;
		while (s <= e) {
			int m = (s + e) / 2;

			// 중앙값이 b보다 큰 경우
			if (a[m] > b) {
				e = m - 1;
			}
			// 중앙값이 b보다 작거나 같은 경우
			else {
				s = m + 1;
			}
		}
		return n - s;
	}
}