[백준]13392: 구간 나누기2 - JAVA

[백준]13392: 구간 나누기2

13397번: 구간 나누기 2

풀이

🪑 최댓값의 최솟값! 을 구하는 문제. 이런 문제는 "이분 탐색" 으로 풀 수 있는 문제들이다. (최단거리는 BFS를 떠올리듯..)

 

먼저 문제의 조건들을 정리해보자.

• N개의 수를 M개 이하의 구간으로 나눠 구간 점수의 최대 값의 최소값을 구한다.
• 구간 점수는 구간에 속한 수의 최대값 에서 최소값을 뺀 값이다.
• N개의 수를 나눌 때는 연속된 순서대로 나눠지면, 각 구간은 한개 이상의 수를 포함한다. (한개도 가능)
• 수가 하나도 빠짐 없이 구간에 포함되어야 한다.

 

🔧 이제 문제 풀이 과정을 생각해 보자.

1. 이분탐색을 진행한다. 이때 탐색하는 범위는 구간에서 발생할 수 있는 최소 ~ 최대값 사이이며, 탐색에서 사용하는 중앙값이 문제에서 구하고자 하는 최대값의 최소값이 된다.
2. mid가 최소가 될 수 있도록 M개 이하로 나눌 수 있는지 확인한다.
3. 나눌 수 있다면, 더 작은 범위를 탐색한다.
4. 나눌 수 없다면, 더 큰 범위를 탐색한다.

 

🔹 이분탐색을 진행한다.

- 범위 지정을 위해 입력받는 값의 최소, 최대값을 저장해 주었다. 최소한의 범위만 탐색해 주기 위함이다.

- mid 값이 문제에서 구하고자 하는, 최대 값의 최속값이 된다.

- mid로 m개 이하의 구간으로 나눌 수 있는지 여부에 따라 탐색 범위를 조정해 주었다.

 

🔹 mid가 최소가 될 수 있도록 M개 이하로 나눌 수 있는지 확인한다.

- canDivideByMid 함수를 구현해 주었다.

- 초기 구간의 개수는 1개이며, 초기 mid, max값은 배열의 첫 번째 값으로 초기화 해 주었다.

- 반복문을 통해 배열의 구간을 탐색한다. 이때 최대값 - 최소값이 mid보다 커지면 mid가 최소가 될 수 있는 구간이 될 수 없으므로 구간의 개수를 하나 늘려 주고 mid, max값도 현재 값으로 변경해 주며 구간을 나눠준다.

- 구간의 개수가 M보다 커지면 false를 반환한다.

 

 

코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int n = scan.nextInt();
        int m = scan.nextInt();
 
        int[] nums = new int[n];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
            min = Math.min(nums[i], min);
            max = Math.max(nums[i], max);
        }
 
        int left = 0;
        int right = max - min;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(canDvideByMid(mid, m, nums)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(left);
    }
 
    public static boolean canDvideByMid(int mid, int m, int[] nums) {  
        int countSet = 1;
        
        int min = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
            if((max - min) > mid) {
                min = nums[i];
                max = nums[i];
                countSet++;
                if(countSet > m) return false;
            }
        }
        return true;
    }
}