백준 - 6549 히스토그램에서 가장 큰 직사각형 [JS]

문제

백준 - 6549

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

입력

• 각 줄
  • 테스트 케이스
  • 직사각형의 수 n, 히스토그램 h1, ..., hn
• 마지막 줄
  • 0, 끝을 의미

제한 사항

• 1 ≤ n ≤ 100,000
• 0 ≤ hi ≤ 1,000,000,000
• 모든 직사각형의 너비는 1

예시

// NOTE: 입력
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

// NOTE: 출력
8
4000

해결

내가 생각하는 분할 정복의 포인트는 재귀 + 횟수 + 범위 정하기인데
범위를 얼마나 잘라서 어떤걸 재귀돌릴 지 모르겠어서 문제다
그래서 다른 분의 풀이를 많이 참고했다

[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]

무엇을 기준으로 분할할 것인가?

• 가운데!

가장 높은 또는 가장 낮은 그래프를 기준으로 할 수 있지만,
탐색 범위가 넓으면 Math.max와 Math.min 부적합하다. 완전탐색이기 때문이다.
시작부터 힘빼는 느낌

반으로 분할하자

분할 후 동작

• 왼쪽 범위의 max, 오른쪽 범위의 max, 왼쪽+오른쪽 병합한 범위의 max 비교
• 가장 큰 값 반환

왼쪽 범위의 max, 오른쪽 범위의 max를 구할 때
이때 재귀를 한다.
조건은 그래프 가로의 너비가 1일 때 까지!

왼쪽+오른쪽 병합한 범위의 max 비교

왼쪽의 max와 오른쪽의 max는 전체 범위의 max라고 장담할 수 없다.
4와 5의 블럭을 예시로 보면,

• 둘 중 max는 5다
• 하지만 4와 5 블럭을 병합하면 max는 8이다(가로 2 X 세로 4)

이런 문제로, 왼쪽과 오른쪽을 병합하여 최대 범위를 구한다.

병합한 범위의 max

가로가 늘어나면 높이는 작아진다

범위를 탐색하면서,
높이를 갱신하고 max를 계산한다.
만약 기존 값보다 계산한 값이 크면 max의 값을 갱신한다.

탐색 방향은 오른쪽 그래프와 왼쪽 그래프의 값을 비교해서
더 큰쪽을 우선으로 탐색한다.

간혹 한쪽의 탐색을 먼저 완료하게 되는 경우,
반대편만 집중적으로 탐색해주면 된다.

전체 코드

const _cases = require('fs')
	.readFileSync('dev/stdin')
	.toString()
	.trim()
	.split('\n');
_cases.pop();

_cases.forEach(v => {
    const [n, ..._histogram] = v.split(' ').map(v => +v);
    
    const getMax = (low, high) => {
        // NOTE: 가로 너비 1인 경우
        if (low == high) return _histogram[high];
    
        // NOTE: 좌우 반갈죽 너비 비교해서 큰 너비 저장
        const _mid = Math.floor((low + high) / 2);
        const _leftMax = getMax(low, _mid);
        const _rightMax = getMax(_mid + 1, high);
    
        return Math.max(_leftMax, _rightMax, getMergeMax(low, high, _mid));
    }
    
    const getMergeMax = (low, high, mid) => {
        const _pointer = { left: mid, right: mid };
        let _height = _histogram[mid];
        let _max = _histogram[mid];
    
        // NOTE: 범위 내 탐색
        while(low < _pointer.left && _pointer.right < high) {            
            if (_histogram[_pointer.left - 1] < _histogram[_pointer.right + 1]) {
                _height = Math.min(_height, _histogram[++_pointer.right]);
            } else {
                _height = Math.min(_height, _histogram[--_pointer.left]);
            }
            
            _max = Math.max(_max, _height * (_pointer.right - _pointer.left + 1));
        }
        
        // NOTE: 우측 탐색 완료한 경우
        while(low < _pointer.left) {
            _height = Math.min(_height, _histogram[--_pointer.left]);
            _max = Math.max(_max, _height * (_pointer.right - _pointer.left + 1));
        }
        
        // NOTE: 좌측 탐색 완료한 경우
        while(_pointer.right < high) {
            _height = Math.min(_height, _histogram[++_pointer.right]);
            _max = Math.max(_max, _height * (_pointer.right - _pointer.left + 1));
        }
        
        return _max;
    }
    
    console.log(getMax(0, n - 1));
});