[BOJ] 7795번: 먹을 것인가 먹힐 것인가

1. 문제

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

• (1 ≤ N, M ≤ 20,000) 
• 정답의 최대치

모든 쌍이 정단인 경우 => N * M = 20,000 * 20,000 = 4*10^8 = 4억 => Integer 사용 가능

 

2. 시간복잡도

(1) 완전탐색

• A 배열 (N) 에서 하나씩 선택해서 B 배열 (M) 전부 탐색

O(NM) = 20,000 * 20,000 = 4억 => (4초) 시간초과

(2) 이분탐색

1. B 배열 정렬 한번 => O(MlogM)
2. 모든 A의 원소마다, B 배열에 대해 이분 탐색 필요 => O(NlogM)
총 시간복잡도 : O((N + M)logM) = (20,000 + 20,000)log(20,000) = 약 60만 (1초 시간안에 계산 가능)

 

3. 구현

public class S3_7795 {
    static StringBuilder sb = new StringBuilder();
    static int T;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
        for (int i = 0; i <T; i++) {
            int ans = 0;
            String str = br.readLine();
            st = new StringTokenizer(str, " ");
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int[] A = new int[N+1];
            int[] B = new int[M+1];
            str = br.readLine();
            st = new StringTokenizer(str, " ");
            for (int j = 1; j <= N; j++) {
                A[j] = Integer.parseInt(st.nextToken());
            }
            str = br.readLine();
            st = new StringTokenizer(str, " ");
            for (int j = 1; j <= M; j++) {
                B[j] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(B, 1, M+1);
            for (int j = 1; j <=N; j++) {
                ans +=binarySearch(B, 1,M, A[j]);
            }
            sb.append(ans).append("\n");
        }
        System.out.println(sb.toString());
    }

    // 배열 B에서 X 미만의 수(X 보다 작은 수) 중 제일 오른쪽 인덱스를 return 하는 함수
    // 그런 게 없다면 L - 1을 return 한다.
    static int binarySearch(int[] B, int L, int R, int X) {
        int result = L-1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if(B[mid] < X) {
                result = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return result;
    }
}