[알고리즘] 다양한 이분 탐색 문제 풀이

2차 배열 이분 탐색

row 값과 cols값을 구하기만 한다면 문제는

import java.io.IOException;
​
public class Main {
​
    private static boolean solution(int[][] arr, int target) {
        if (arr == null || arr.length == 0) {
            return false;
        }
​
        int left = 0;
        int rows = arr.length;
        int cols = arr[0].length;
        int right = rows * cols - 1;
​
        while (left <= right) {
​
//            배열 전체 길이의 중간 값
            int mid = left + (right - left) / 2;
            
//            mid / cols = row 값
//            mid % cols = cols 값
            
            if (arr[mid / cols][mid % cols] == target) {
                return true;
            } else if (arr[mid / cols][mid % cols] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
​
    public static void main(String[] args) throws IOException {
        int[][] arr = {{1, 2, 3}, {5, 10, 11}, {20, 30, 40}};
​
        System.out.println(solution(arr, 30));
        // true
        System.out.println(solution(arr, 4));
        // false
    }
}

최소한의 적재량을 이분 탐색으로 계산

정수형 배열 arr와 정수 days가 주어진다.

arr에는 각 상품의 무게의 정보, days는 운송 납기일

상품을 순서대로 담아서 운송해아하는데, days 이내에 운송을 하기 위한 최소한의 적재량을 계산해보자.

import java.io.IOException;
​
public class Main {
​
    private static int solution(int[] arr, int days) {
        int minWeight = 0;
        int maxWeight = 0;
​
//        minWeight = 1개만 담았을 때의 최댓값
//        maxWeight = 한 번에 모두 담았을 때의 최댓값
        for (int a : arr) {
            minWeight = Math.max(minWeight, a);
            maxWeight += a;
        }
​
        while (minWeight <= maxWeight) {
            int carryingWeight = (minWeight + maxWeight) / 2;
​
            int countDays = 1;
            int cur = 0;
​
            for (int weight : arr) {
                //현재까지 담은 무게가 적재량보다 크면
                //이동한 날짜 증가 및 누적 무게 초기화
                if (cur + weight > carryingWeight) {
                    countDays++;
                    cur = 0;
                }
                cur += weight;
            }
            //현재 적재량으로 이동한 날짜가 주어진 날짜보다 크면
            //현재 적재량이 부족하기 때문에 적재량 증가
            if (countDays > days) {
                minWeight = carryingWeight + 1;
            }
            //현재 적재량이 넉넉하기 때문에 적재량 감소
            else {
                maxWeight = carryingWeight - 1;
            }
​
        }
​
        //최소 적재량
        return minWeight;
    }
​
    public static void main(String[] args) throws IOException {
        int[] arr = {3, 2, 2, 4, 1, 4};
​
        System.out.println(solution(arr, 3)); // 6
    }
}