떡볶이 떡 만들기 문제

이진 탐색
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법

✅ 문제

한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력 예시
4 6
19 15 10 17

출력 예시
15

💻 코드

import java.util.*;

public class TestJava6
{
    public static int binarySearch(int[] arr, int target, int start, int end)
    {
        int result = 0;
        while(start <= end)
        {
            long total = 0;
            int mid = (start + end) / 2;
            for(int i = 0; i < arr.length; i++)
            {
                if (arr[i] > mid)
                    total += arr[i] - mid;
            }
            if(total < target)
                end = mid - 1;
            else {
                result = mid;
                start = mid + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine(); // 버퍼 제거

        ArrayList<Integer> arrayList = new ArrayList<>();
        for(int i = 0; i < n; i++)
        {
            int temp = sc.nextInt();
            arrayList.add(temp);
        }

        Collections.sort(arrayList);
        int pr = binarySearch(arrayList.stream().mapToInt(i -> i).toArray(), m, 0, arrayList.get(n-1));
        System.out.println(pr);
    }
}

📝 정리

입력 조건이 개수가 상당히 많을 시에 이진 탐색 활용하기.

📌참고

[Java] Integer ArrayList을 int 배열로 변환 방법
https://velog.io/@deannn/Java-int%ED%98%95-ArrayList-%EB%B0%B0%EC%97%B4-%EB%B3%80%ED%99%98

public static void main(String args[]) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    
    // 방법 1
    int[] arr1 = new int[list.size()]
    for (int i = 0 ; i < list.size() ; i++) {
        arr1[i] = list.get(i).intValue();
    
    // 방법 2
    int[] arr2 = list.stream()
                .mapToInt(i -> i)
                .toArray();
    
    // 방법 3
    int[] arr3 = list.stream()
                .mapToInt(Integer::intValue)
                .toArray();

    // 방법 4
    int[] arr4 = list.stream()
                .filter(i -> i != null)
                .mapToInt(i -> i)
                .toArray();
}