[BOJ/백준] 7795 먹을 것인가 먹힐 것인가 (S3)

문제

https://www.acmicpc.net/problem/7795

풀이

A의 요소와 B의 요소를 비교하면서 A의 요소가 B의 요소보다 큰 경우의 개수를 구한다.

 

처음에 A의 요소와 B의 요소를 배열로 받고 이중 for문으로 직접 비교하니 시간 초과가 떠서 B의 요소를 Arrays.sort()로 정렬을 한 뒤, B의 요소를 이분탐색하며 A의 요소와 비교하는 방법을 사용했다.

Code

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        StringBuilder result = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); //테스트케이스 수

        for(int t=0;t<T;t++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            int[] A = new int[N];
            int[] B = new int[M];

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

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

            Arrays.sort(B);
            int temp = 0;
            for(int i=0;i<N;i++) {  // B에 대하여 이분탐색
                int low = 0;
                int high = M-1;  // B의 마지막 인덱스
                int cnt = 0;
                while(low<=high) {
                    int mid = (low+high)/2; //중간값
                    if(B[mid]<A[i]) {  // B의 중간값이 현재 위치의 A값보다 작으면
                        low = mid+1;  // 적절한 위치로 low값 조정
                        cnt = mid+1;  // 인덱스 상으로 현재 mid+1이 A값보다 작은 것의 개수이므로 일단은 cnt에 추가
                    }
                    else
                        high = mid-1;  // 적절한 위치로 high값 조정
                }
                temp+=cnt;
            }
            result.append(temp+"\n");
        }

        bw.write(result+"");
        bw.flush();
        bw.close();
    }
}