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

1. 문제

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

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

 

2. 풀이

이분탐색을 이용하는 문제이다. 각각의 테스트 케이스 별로 A 배열과 B 배열이 주어졌을 때 선택 당해지는 배열인 B 배열을 정렬한 후 이분탐색을 진행한다. 탐색의 대상은 B 배열의 인덱스인데 이때의 핵심은 탐색이 끝났을 때 결과인 index 값이 선택된 A의 값보다 작은 B 요소의 개수라는 것이다. 탐색이 끝났을 때 B[index]의 값은 선택된 A값의 요소보다 작은 값 중에서 가장 큰 값이기 때문에 이 보다 작은 인덱스의 B 배열 값은 탐색할 필요 없이 작은 값이라는 이야기이다.

위의 방법대로 이분 탐색을 이용하는 방법이 문제에서 요구하는 정석적인 방법이다. 그러나 문제를 해결하고 다시 읽어보니 N과 M의 개수가 각각 최대 20,000개 까지 입력될 수 있었다. 그래서 A 배열과 B 배열을 정렬한 후 브루트포스로 제출하였더니 정답 처리가 되었다. 물론 이분 탐색보다 시간이 오래 걸리는 방법이고 이 문제에서는 탐색해야 하는 최대 개수가 20,000 * 20,000으로 그리 많지 않다보니 통과가 된 것이라 짐작한다.

3. 소스 코드 

1. 이분 탐색

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            StringTokenizer 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 j = 0; j < N; j++) {
                A[j] = Integer.parseInt(st.nextToken());
            }

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

            Arrays.sort(B);
            int result = 0;

            for (int j = 0; j < N; j++) {
                int first = 0;
                int end = M - 1;
                int index = 0;

                while (first <= end) {
                    int mid = (first + end) / 2;
                    if (B[mid] < A[j]) {
                        first = mid + 1;
                        index = mid + 1;
                    }
                    else {
                        end = mid - 1;
                    }
                }
                result += index;
            }

            bw.write(Integer.toString(result) + "\n");
        }

       bw.flush();
       bw.close();
       br.close();
    }
}

2. 브루트포스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            StringTokenizer 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 j = 0; j < N; j++) {
                A[j] = Integer.parseInt(st.nextToken());
            }

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

            Arrays.sort(A);
            Arrays.sort(B);

            int result = 0;
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (A[j] <= B[k]) {
                        break;
                    }
                    else {
                        result += 1;
                    }
                }
            }

            bw.write(Integer.toString(result) + "\n");
        }

       bw.flush();
       bw.close();
       br.close();
    }
}