[백준 | Java] 13397 구간 나누기 2

내 풀이

각 구간의 최댓값을 결정해나가며 최적해를 찾기 위해 이분 탐색을 사용한다.

예를 들어, 이 문제를 모든 가능한 구간을 확인하는 브루트 포스로 푼다면 문제에서 주어진 (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N)의 범위를 고려해 최대로 가능한 구간의 개수는 5000개로 O(N^2)인 1초 이상의 시간이 소요되어 비효율적이다.

하지만 이분 탐색을 사용한다면 문제의 특성을 이용해 탐색 범위를 절반으로 가능한 구간별 최댓값의 범위를 좁히고, 그 중 최적의 값을 찾아내어 O(logn)의 시간복잡도로 브루트 포스보다 효율적으로 답을 찾아낼 수 있다.

풀이과정은 다음과 같다.

1. left는 현재 배열에서 최솟값을, right는 현재 배열에서 최댓값으로 설정

2. mid를 사용하여 현재 배열을 M개 이하의 구간으로 나눌 수 있는지 확인

3. min과 max를 사용하여 현재 구간의 최솟값과 최댓값 설정

4. 최댓값과 최솟값의 차가 mid보다 크다면, 현 위치의 요소를 min, max 값으로 재설정해 구간을 나누고 cnt+1

5. 배열의 끝까지 확인 후, 나눠진 구간의 개수cnt와 M을 비교

6. cnt <= M이라면, 최적해를 찾았으므로 right를 감소시켜 더 작은 값 탐색

7. cnt > M이라면, left를 증가시켜 더 큰 값 탐색

8. left가 right보다 커질 때 까지 반복

코드

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

public class Main {
    static int N, M, result;
    static int[] arr;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        int left = 0;
        int right = 0;

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, arr[i]);  // 배열의 최댓값을 right에 입력
        }
        result = right;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (isValid(arr, mid)) {   // mid로 M개 이하의 구간으로 나눌 수 있는지 판단
                result = Math.min(result, mid);
                right = mid - 1;   // right를 조정해 더 작은 값으로 탐색 진행
            } else {  // 나눈 구간이 M개 초과일 때
                left = mid + 1;  // left를 조정해 더 큰 값으로 탐색 진행
            }
        }
        System.out.println(result);
    }

    static boolean isValid(int[] arr, int mid) {
        int cnt = 1;
        int min = arr[0];
        int max = arr[0];

        for (int i = 0; i < N; i++) {
            if (arr[i] < min)
                min = arr[i];
            if (arr[i] > max)
                max = arr[i];
            if (max - min > mid) {   // (최댓값 - 최솟값) <= 중간값 이 되는 지점에서 구간을 나눔
                cnt++;
                min = arr[i];
                max = arr[i];
            }
        }
        return cnt <= M;
    }
}