08. 빗물 트래핑

문제링크

문제 분석

기둥 사이에 물이 차기 위해서는 양옆이 높아야된다는 조건이 있다. 이 조건을 생각하면 의외로 쉽게 문제를 해결할 수 있다.

투포인터 기법을 사용해서 왼쪽, 오른쪽 포인터를 만든다. 그리고 양 옆의 최대값을 비교하면서 포인터를 움직이면 된다.

오른쪽의 최대값이 왼쪽보다 크다면, 왼쪽은 오른쪽으로 이동하면서 물의 양을 셀 수가 있는데 이게 가능한 이유는 오른쪽 기둥의 높이는 언제나 왼쪽보다 높다는게 보장이 되기 때문에 기둥 사이에 공간이 마련될 수 있기 때문이다.

해결

JavaScript

var trap = function(height) {
    let left = 0;
    let right = height.length - 1;
    let lMax = height[left];
    let rMax = height[right];
    vol = 0;
    while (left < right) {
        lMax = Math.max(lMax, height[left])
        rMax = Math.max(rMax, height[right])
        if (lMax <= rMax) {
            vol += lMax - height[left]
            left += 1;
        } else {
            vol += rMax - height[right]
            right -= 1;
        }
    }
    return vol
};