문제 이해

A라는 그룹과 B라는 그룹이 존재한다.
이 때 A에는 여러 가지 숫자가, B에도 여러 가지 숫자가 주어진다.
a가 A의 원소이고 b가 B의 원소일 때, (a,b) 쌍을 만들어야 하는데, 이 때 a의 값은 b의 값보다 커야 한다.(같아도 안된다.)

이 때 만들 수 있는 총 (a,b) 쌍의 개수를 구하는 문제이다.

문제 풀이

여기서 내가 주목했던 점은 모든 (a,b) 쌍을 구하지 않아도 된다는 것이다.

즉, a보다 작은 값 중 가장 큰 b값을 구한다면 바로 (a,b)의 쌍의 개수를 구할 수 있을 것이다.

예를 들어, 3이 a이고 B에 1,2,4,6이 있을 경우, 내가 2를 빠르게 찾을 수 있다면 자연스럽게 2개의 (3,x)쌍이 존재한다는 것을 알 수 있을 것이다.

특정 조건에서의 최대값을 찾는 알고리즘? 나는 Parametric Search를 활용하여 풀기로 결정하였다.

코드

import java.util.*;

public class Main {
	
	static Integer bin_search(int left, int right, int[] B, int value) {
		int mid = 0;
		int ans = -1;

		while(left <= right) {
			mid = (left+right)/2;
			if(value > B[mid]) {
                // 조건을 만족 시키는 경우(A > B)
                // 해당 index를 mid에 저장 & mid 왼쪽은 볼 필요 없음
				ans = mid;
				left = mid + 1;
			}
			else {
                // 조건을 만족 시키지 못하는 경우(A <= B)
                // mid 오른쪽은 볼 필요 없음
				right = mid - 1;
			}
		}
        /*
        ans에는 조건을 만족 시키는 Case중 가장 작은 index가 저장되어 있을 것이다
        0 ~ ans까지의 index가 (a,b) 쌍을 만들 수 있는 값이 될 것이다.
        따라서 ans - 0 + 1 = ans + 1로 답을 반환한다.

        만약 (a,b) 쌍이 없을 경우 위에서 처음으로 지정했던 ans = -1이 
        넘어오기 때문에 -1 + 1 = 0이 반환 될 것이다.
        */

		return ans + 1;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int t =0;t<T;t++) {
			
			int N = sc.nextInt();
			int M = sc.nextInt();
			
			int[] A = new int[N];
			int[] B = new int[M];
			
			for(int i =0;i<N;i++) {
				A[i] = sc.nextInt();
			}
			
			for(int i =0;i<M;i++) {
				B[i] = sc.nextInt();
			}

			Arrays.sort(B); 
            // A원소의 값을 가지고 B array에 대해 Binary Search를 하기 때문에
            // B만 Sorting시키면 된다.
			
            int answer = 0;
			for(int i =0;i<N;i++) {
				answer+=bin_search(0,M-1, B, A[i]);
			}
			System.out.println(answer);
		}
	}
}

결과