문제 탐색하기

입력 자료 정리

1. n은 배열의 크기, m은 나눠져야하는 구간의 개수를 말한다
2. 이어서 n만큼 들어오는 값은 배열의 원소값이다

해결방법 추론

1. 전체 범위가 작기 때문에, 브루트포스나 백트래킹을 고려해볼만한 문제다
2. 하지만 해당 방법으로는 구간을 나누기 쉽지 않았고,
   다른 방법을 고민했는데, 선택한 방법은 이분탐색이다
3. 최댓값을 기준으로 해서 최솟값을 구하는 이분탐색을 한다면,
   원하는 결과를 찾을 수 있을 것이다
4. 정해둔 최댓값보다 큰 경우가 있다면,
   해당 구간 이전까지로 나눠줘서 최댓값보다 큰 구간이 나오지 않도록 한다
5. 이렇게 했을 때 구간의 개수를 세어줘서 이분탐색을 하는 것을 추론하였다

시간복잡도 계산

1. 이분탐색에서 발생한 시간복잡도는 O(n x log원소값)이 될 것이며
   시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. n과 m은 변수로 관리하고, 각 값은 int형 1차원 배열로 관리한다
2. left는 0으로, right는 원소중 가장 큰 값으로 갱신한다
3. 정답은 최댓값의 최솟값을 찾야하므로 Integer.MAX_VALUE로 초기화한다

구현 코드 설계

1. 이분탐색 동안에, 구간안에서의 최댓값과 최솟값의 차이를 구하기 위해
   별도의 변수 l과 r을 만들었다.
2. 각각 배열의 원소를 확인하며 최솟값과 최댓값을 갱신하고,
   둘의 차이를 비교하여 mid보다 큰지 확인한다
3. 만약 크다면 mid보다 큰 최댓값이 나오면 안되기 때문에,
   해당 지점부터 다시 범위를 시작하도록 갱신하고, 구간이 나눠졌기 때문에 count값을 증가한다
4. count가 m보다 크면 최댓값을 너무 작게 해서 그런것이므로 left를 조절하고
   반대는 right를 조절해서 최적의 수를 찾는다
5. 또한 right를 조절하며 정답도 갱신해주는데, m보다 작을 때도 정답으로 할 수 있는 이유가
   현재 구간 안에서 어떻게 구간을 나눠도 최댓값보다 큰 값이 나올 수 없기 때문이다
6. 따라서 이러한 이분탐색 과정을 통해 ans를 갱신해준다

출력값 설계

1. 완성한 ans를 출력하면 정답이 된다.

추가 테스트케이스

테스트케이스 1

입력

1 1
10000

결과

• 예상 출력값 0

테스트케이스 2

입력

5 5
1 2 3 4 5

결과

• 예상 출력값 0

테스트케이스 3

입력

3 2
39 24 13

결과

• 예상 출력값 11

정답 코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] 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]);
        }
        int ans = Integer.MAX_VALUE;
        while(left <= right){
            int mid = (left + right) / 2;
            int l = 10_001;
            int r = 0;
            int count = 1;
            for (int i = 0; i < n; i++) {
                l = Math.min(l, arr[i]);
                r = Math.max(r, arr[i]);
                if(r - l > mid){
                    l = 10_001;
                    r = 0;
                    count++;
                    i--;
                }
            }

            if(count > m){
                left = mid + 1;
            }else{
                right = mid -1;
                ans = Math.min(ans, mid);
            }

        }

        bw.write(ans+"");

        br.close();
        bw.close();
    }
}

문제 링크

13397번 - 구간 나누기 2