문제
풀이
문제 정의
N개의 수로 이루어진 1차원 배열이 있고, 이 배열을 M개 이하의 구간으로 나눠야 한다.
각 구간에서 최댓값 - 최솟값을 "구간의 점수"라고 한다.
이때 모든 구간의 점수중 최댓값이 있을 것이다. 그 중 최솟값을 구하는 문제다.
해결 방안
처음엔 완전탐색을 떠올렸다. 하지만 완전탐색을 수행하기에는 범위가 너무 컸다. 그래서 DP를 생각했는데 DP로도 적절한 방법이 떠오르지 않았다.
결국 도무지 해결방안이 떠오르지 않아 다른 블로그를 참고했다.
이 문제는 이진탐색을 응용한 매개 변수 탐색 알고리즘으로 푸는 문제였다.
우선 코드를 먼저 보자.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const arr = input[1].split(' ').map(Number);
let answer = 0;
function binarySearch(mid) {
let count = 1;
let max = -Infinity;
let min = Infinity;
for (let i = 0; i < N; i++) {
max = Math.max(arr[i], max);
min = Math.min(arr[i], min);
if (max - min > mid) {
count++;
max = arr[i];
min = arr[i];
}
}
return count;
}
let [min, max] = [0, Math.max(...arr)];
while (min <= max) {
let mid = (min + max) >> 1;
let count = binarySearch(mid);
if (count <= M) {
max = mid - 1;
answer = mid;
} else min = mid + 1;
}
console.log(answer);우리는 mid라는 변수로 구간의 점수의 최댓값의 최솟값을 구해줄 것이다.
그러기 위해선 mid를 모든 구간의 최댓값이라고 '가정'을 해야 한다. 그리고 min, max로 가능한 값의 범위를 설정해주고, 이진 탐색과 동일하게 mid = Math.floor((min + max)/2) === (min + max) >> 1로 설정해주고
let [min, max] = [0, Math.max(...arr)];
while (min <= max) {
let mid = (min + max) >> 1;
...
}예를 들어 1 5 4 6 2 1 3 7 라는 입력값이 주어졌다면 min = 0, max = 7, mid = 3 이 된다.
그리고 구간 나누기를 수행할binarySearch 함수에 mid를 전달해준다.
function binarySearch(mid) {
let count = 1;
let max = -Infinity;
let min = Infinity;
for (let i = 0; i < N; i++) {
max = Math.max(arr[i], max);
min = Math.min(arr[i], min);
if (max - min > mid) { // 구간 분리
count++;
max = arr[i];
min = arr[i];
}
}
return count;
}
...
let count = binarySearch(mid);
...현재 mid === 3이다. 또한 mid는 모든 구간의 점수중 최댓값이라고 가정했다. 따라서 구간을 나눌 때 구간의 점수가 mid를 넘는다면 이전 까지의 구간을 분리한다.
1 5 4 6 2 1 3 7가 있을 때를 가정해보자.
- 1->5: 5-1=4는 3보다 크기 때문에 구간을 분리한다.
(1) 5 4 6 2 1 3 7 - 5->4->6->2: 6-2=4는 3보다 크기 때문에 구간을 분리한다.
(1) (5 4 6) 2 1 3 7 - 2->1->3->7: 7-1=6은 3보다 크기 때문에 구간을 분리한다.
(1) (5 4 6) (2 1 3) 7 - 7
(1) (5 4 6) (2 1 3) (7)
이렇게 하면 어떤 구간의 점수도 mid보다 커지지 않는다. 그리고 그때의 구간의 개수(count)를 리턴한다.
while (min <= max) {
...
let count = binarySearch(mid);
if (count <= M) {
max = mid - 1;
answer = mid;
} else min = mid + 1;
}M === 3이라고 했을 때, 현재 count === 4가 M 보다 크기 때문에 min을 증가시켜서 mid의 값을 키움으로써 구간의 개수를 줄여야 한다.
따라서 min = 4, max = 7, mid = 5 가 되고,
구간은 (1 5 4 6 2 1 3) (7)로 나눠진다.
count === 2이므로 M개 이하다.
구간의 개수가 M개 이하일 때 mid는 정답의 후보가 될 수 있으므로 answer 변수에 mid를 저장한다. (answer = 5)
하지만 아직 max 를 줄여서 mid 의 값을 더 작아지게 만들 수 있으므로 현재의 mid 가 최솟값인지는 아직 모른다.
따라서 max = mid - 1 로 감소시킨다.
이어서 진행해 보면,
min = 4, max = 4, mid = 4
구간 = (1 5 4) (6 2) (1 3) (7)
count = 4구간의 개수가 M보다 많으므로
min = mid + 1 = 5min이 max보다 커졌으므로 반복문이 종료되고 정답인 5가 출력된다.
코드
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const arr = input[1].split(' ').map(Number);
let answer = 0;
function binarySearch(mid) {
let count = 1; // 구간의 개수
let max = -Infinity;
let min = Infinity;
for (let i = 0; i < N; i++) {
max = Math.max(arr[i], max);
min = Math.min(arr[i], min);
// 5
if (max - min > mid) {
count++;
max = arr[i];
min = arr[i];
}
}
return count;
}
let [min, max] = [0, Math.max(...arr)]; // 1
while (min <= max) {
let mid = (min + max) >> 1; // 2
let count = binarySearch(mid);
// 3
if (count <= M) {
max = mid - 1;
answer = mid; // 4
} else min = mid + 1;
}
console.log(answer);
// 1. 최댓값중 최솟값의 가능한 범위 min ~ max
// 2. mid는 모든 구간의 점수중 최댓값이라고 가정함.
// 3. 구간의 개수가 M개 이하라면 그때의 mid가 정답 후보. 하지만 mid가 더 작아질 수 있으므로 계속해서 진행
// 4. max가 작아지면 mid도 작아짐. 또한 max는 작아지기만 하기 때문에 마지막 mid 값이 최댓값중 최솟값이 됨.
// 5. mid가 모든 구간의 점수중 최댓값이라고 가정했기 때문에 max-min > mid일 경우 구간을 분리해줌.
