42. Trapping Rain Water

LeetCode 42번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Trapping Rain Water - LeetCode

풀이

아이디어

물이 고이기 위해선 -> 양 옆에 자기보다 높은 벽이 있어야 한다.

물의 양은 min(왼쪽 최대 높이 - 오른쪽 최대 높이) - 현재 높이 로 결정된다.

각 한 칸 한 칸 마다 고일 수 있는 물의 양을 구한다는 생각으로 문제를 풀면 된다.

코드

function trap(height: number[]): number {
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0;
    let total = 0;

    while (left < right) {
        if (height[left] <= height[right]) {
            // 왼쪽으로
            leftMax = Math.max(leftMax, height[left]);
            total += leftMax - height[left];
            left++;
        }
        else {
            rightMax = Math.max(rightMax, height[right]);
            total += rightMax - height[right];
            right--;
        }
    }

    return total;
};