문제

구간 나누기 2

풀이

이분탐색으로 푸는 문제인데 솔직히 바로 이분탐색이 떠오르지 않았다. 이분탐색으로 구해야 하는 이유는 최대값의 최소값을 구하는 문제이기 때문에 가장 중간 값을 구할수 있는 기준값을 구할때 가장 최적의 시간에 구할 수 있다

1. 이분 탐색으로 유효한 값에 해당하는 answer를 갱신해준다

		int answer = right;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (isValid(arr, mid)) {
                answer = Math.min(answer, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

2. m개 이하로 구간의 개수가 만족 될때만 통과될수 있도록 합니다.

	private 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;
    }

전체 코드

전체 코드