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

조건

1. 맨 처음 입력되는 줄은 테스트 케이스의 개수인 T가 주어진다

2. 텍스트 케이스 A와 B의 수는 N 과 M이다.

3. 각각 텍스트 케이스 내부의 정수들을 입력받는다.

4. A에 있는 정수는 B에 정수들과 쌍을 이룰 수 있는데 A의 수보다 작아야 한다.

예제 입력

해설

해당 문제를 가장 쉽게 푸는 방법은 A의 배열에서 순서대로 하나를 선택해 B 전체를 돌며 하나하나 비교하는 것이다. 그렇게 된다면 시간 복잡도는 O(N M) 과 같다 하지만 그렇게 된다면 N과 M의 최대 개수는 2만개이다 20,000 20,000는 4억이 나오고 초당 1억을 해결 한다는 가정에 4초가 되므로 시간초과로 해당 문제를 풀지 못한다.

그렇다면 어떻게 해야할까 여기서는 2가지를 할 것이다 첫 번째는 B를 정렬할 것 이다.
정렬의 특징인 좌 우 에 자신과 비슷한 값을 가진 것들이 분포한다는 특징을 이용해
이진탐색을 할 것이다. 그렇게 한다면 시간 복잡도는 O(N log N)이므로 시간 복잡도를 획기적으로 줄일 수 있다.

코드

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static int[] A, B;

    static void input() { 
    
        N = scan.nextInt(); // A의 개수를 받아온다.
        M = scan.nextInt(); // B의 개수를 받아온다.
        
        A = new int[N + 1]; // 배열 index 탐색을 1부터 하기 위해 1을 더해줌
        B = new int[M + 1]; // 배열 index 탐색을 1부터 하기 위해 1을 더해줌
       
       for (int i = 1; i <= N; i++) {
            A[i] = scan.nextInt(); // A의 값들을 받아 입력해준다.
        }
        
        for (int i = 1; i <= M; i++) {
            B[i] = scan.nextInt(); // B의 값들을 받아준다.
        }
    }

	// 해당 메소드는 배열의 값 , 인덱스 맨 왼쪽의 값 , 인덱스 맨 오른쪽 값,
    // 비교할 A의 값
    static int findAns(int[] A, int L, int R, int X) {
        
        int res = L - 1; //해당 되는 값이 없다면 0을 return 해주기 위해 
        				// L - 1을 지정해준다.
        while (L <= R) { // 조건이 성립한다면 끝과끝의 인덱스가 겹쳐지기 전까지 반복한다.
            int mid = (L + R) / 2; // mid값을 인덱스의 중간값으로 해준다.
            if (A[mid] < X) { // 값들을 비교해준다. 
                res = mid;  // 만약 비교값보다 작다면 res에 mid값을 넣어주고
               L = mid + 1; // 그리고 이미 mid아래값은 작기 때문에 더 이상 비교할 필요가 없다 L index의 값을 mid + 1을 해줘서 mid 값 이후를 다시 비교해준다.
            } else {
                R = mid - 1; // 만약 비교값 A 보다 크다면 R index값을 mid - 1 로 설정해줘서 mid 아래의 값들을 다시 비교해준다.
            }
        }
        return res;
    }

    static void find() {
     
        Arrays.sort(B, 1, M + 1); // B의 값들을 오름차순으로 정렬해준다.
        
        int ans = 0; 
        for (int i = 1; i <= N; i++) {
            ans += findAns(B, 1, M, A[i]); // B에서의 값들을 받아서 ans에 넣어준다.
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        int TT;
        TT = scan.nextInt(); // 전체 테스트 케이스 개수를 받아온다.
        for (int tt = 1; tt <= TT; tt++) {
            input(); // 입력값들을 받아준다.
            find();  // find() 함수를 실행한다.
        }
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}