[백준] 13397. 구간 나누기 2 (이분탐색/Java)

[백준] 13397. 구간 나누기 2

📌 풀이 과정

배열을 M개 이하의 구간으로 나눌 때, 각 구간의 점수(최댓값-최솟값)의 최댓값 중 최솟값을 구하는 문제다.

이 문제도 이분 탐색을 활용하는 문제인건 파악했으나.. 코드 작성하기 까지 조금 헤맸다.

 

이분 탐색을 활용하는 이유

• 구하고자 하는 것이 최댓값의 최솟값
• 특정 값으로 가능한지 여부를 판단할 수 있다. (Yes/No 문제)
• 값이 커질수록 구간을 M개 이하로 나누기 쉽다.

이분 탐색 범위

최소값: 0 (구간의 점수가 가질 수 있는 최솟값)

최대값: 배열의 최댓값 - 최솟값 (전체 배열에서 가능한 최대 점수)

 

판단 방법

1. mid값을 구간의 최대 점수라 하자.
2. 배열을 순회하면서 현재 구간의 점수(최댓값 - 최솟값)이 mid를 초과하면 새로운 구간 시작
3. 이렇게 나누어진 구간의 개수가 M개 이하인지 확인
   • M개 이하로 나누어지면 -> 더 작은 값 시도 (right = mid - 1)
   • M개 초과로 나누어지면 ->  더 큰 값 필요 (left = mid + 1)

 

 

✨ 제출 코드

메모리: 15232 KB

시간: 136 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 배열의 크기
        int M = Integer.parseInt(st.nextToken()); // 구간 갯수
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }

        int left = 0;
        int right = max - min;
        int answer = 0;

        while(left <= right){
            int mid = (left + right) / 2;
            int curMin = arr[0];
            int curMax = arr[0];
            int cut = 1;

            for(int i = 1; i < N; i++){
                curMin = Math.min(curMin, arr[i]);
                curMax = Math.max(curMax, arr[i]);

                if(curMax - curMin > mid){
                    cut++;
                    // 새로운 구간 최소값, 최대값 갱신
                    curMin = arr[i];
                    curMax = arr[i];
                }
            }

            if(cut <= M) { // M개 이하로 나눌 수 있다
                answer = mid;
                right = mid - 1; // 더 작은 값도 가능한지
            }
            else{
                left = mid + 1; // 더 큰 값 필요
            }
        }

        System.out.println(answer);
    }
}