백준 7795 - 먹을 것인가 먹힐 것인가

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

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

 

* 문제 요약

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다.

예를 들어 A의 크기가 {8, 1, 7, 3, 1} 이고, B의 크기가 {3, 6, 1} 인 경우에 A가 B를 먹을 수 있는 쌍의 갯수는 7가지가 있다. 

(8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1)

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇개나 있는지 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 테스트 케이스의 갯수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다.

둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다.

(1 <= N <= 20,000)

 

* 출력

각 테스트 케이스마다 A가 B보다 큰 쌍의 갯수를 출력한다.

 

* 예시

 

* 해결 과정

매 반복마다 B에서 현재 탐색중인 A의 특정값 크기보다 더 작은 값들의 갯수를 찾아서 합산해줘야 한다.

여기서 B를 오름차순으로 정렬해준 다음, B에 대해 중복이 존재하는 배열에서 최초로 특정값이 나오는 경우 해당 위치를 반환해주는 lowerBound 방식의 이분탐색을 수행해준 다음, 찾아낸 위치 -1 값을 돌려주면 해당 위치가 바로 현재 탐색중인 A의 특정값 보다 작은 값들 중 가장 큰 값의 위치에 해당된다.

 

이렇게 lowerBound 를 통해 특정 인덱스를 반환받은 다음, 배열 인덱스의 특징을 고려해 해당 값에 +1을 해준 값을 total 변수에 합산해주는 방식을 A의 모든 값에 적용시켜 주었고, 이를 통해 얻은 최종 total 값을 출력 시켜주는 것으로 문제를 해결하였다.

 

A안에 같은 값이 존재할 경우 최초 한번만 이분탐색을 하고 해당값을 따로 저장해준 다음 같은 값이 다시 한번 나왔을 때 해당값을 그대로 활용해주고 싶어도(DP 의 메모이제이션 개념 활용) 물고기 크기의 최대값을 문제에서 제시해주지 않았기 때문에 배열을 활용해서 해당값을 저장해주기도 애매했고, 그렇다고 해시맵을 사용하자니 메모리를 과도하게 사용하게 될 우려가 있어 특정 크기를 기준으로 했을 때 먹을 수 있는 먹이의 갯수를 따로 저장해주지 못했다,

 

결국 이미 이전에 먹을 수 있는 먹이의 갯수를 구했던 값이 다시 나타나더라도 그때그때 무조건 이분탐색을 수행해주는 방향으로 문제를 해결했다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static int[] arrayA = null;
    static int[] arrayB = null;

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());

        for (int i = 0; i < tc; i++) {
            String[] input = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);

            arrayA = new int[n];
            arrayB = new int[m];
            int total = 0;

            input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                arrayA[j] = Integer.parseInt(input[j]);
            }

            input = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                arrayB[j] = Integer.parseInt(input[j]);
            }

            Arrays.sort(arrayB);

            for (int j = 0; j < n; j++) {
                int number = arrayA[j];

                int index = lowerBound(number);
                // 배열 인덱스의 특징을 고려하여 +1 한 값을 합산해준다.
                total += (index + 1);
            }

            bw.write(total + "\n");
        }

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

    // 중복이 존재하는 배열에서 최초로 특정값이 나오는 경우 바로 왼쪽 위치를 반환해줌
    private int lowerBound(int number) {
        int start = 0;
        int end = arrayB.length;

        while (start < end) {
            int mid = (start + end) / 2;

            if (number <= arrayB[mid]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start - 1;
    }
}

 

현재 A에서 탐색중인 값을 기준으로 오름차순으로 정렬된 B에서 먹을 수 있는 최대 크기의 먹이의 위치를 lowerBound 방식의 이분탐색을 통해 구해준 다음, 해당 위치값을 이용해 먹을 수 있는 먹이의 갯수를 구해주는 방식으로 문제를 해결하였으므로 이분탐색 문제에 해당된다.