LC - 빗물 가두기

문제

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

주어진 배열이 각 블럭의 높이라고 했을 때, 빗물이 가둬진 칸의 갯수를 구하는 문제이다.

풀이

• 각 블럭 중 가장 높이가 높은 블럭을 기준으로, 양 옆으로 Left, Right 포인터를 하나씩 둔다.
• 포인터는 가장 높이가 높은 블럭을 만날 때까지 가운데로 이동한다.
• 포인터가 이동하면서 만났던 블럭 중 가장 높은 블럭에서 현재 블럭의 높이를 빼면 현재 위치에서의 빗물의 높이를 구할 수 있다.
• 가장 높은 블럭이 오른쪽 어딘가에 있다는 걸 확신할 수 있기 때문에, 현재 블럭에서 오른쪽의 높이를 확인하지 않고도 빗물이 갇혀있는지 알 수 있다.
• 오른쪽 포인터를 왼쪽 포인터와 같은 로직으로 구현한다.

코드

var trap = function(height) {
    let result = 0;
    let left = 0;
    let right = height.length-1;
    const maxHeight = Math.max(...height)
    const maxHeightIdx = height.indexOf(maxHeight);
    let leftMax = 0;
    let rightMax = 0;
    
    while(left < maxHeightIdx) {
        leftMax = height[left] > leftMax ? height[left] : leftMax;
        result += leftMax - height[left]
        left++
    }
    
    while(right > maxHeightIdx) {
        rightMax = height[right] > rightMax ? height[right] : rightMax;
        result += rightMax - height[right]
        right--
    }
    
    
    return result;
};