[Leetcode] 42. Trapping Rain Water

오늘의 문제는 아니지만 문제가 좋은 것 같아 풀어본 문제. 음수가 아닌 정수 배열 height 가 주어진다. 각 셀의 값은 벽돌의 높이를 나타낸다. 비가 온다고 했을 때 벽돌들 사이에 물이 얼마나 고이는지 찾아내는 문제.

물은 양 옆의 두 벽 중 낮은 벽의 높이까지만 찰 수 있으므로 먼저 배열을 한 번 돌면서 해당 셀의 제일 오른쪽에 있는 높은 값인rightMax 을 별도의 배열에 저장해두고 두번째로 배열을 돌면서 leftMax 와 rightMax 를 비교한 값을 더해가면 된다.

알고리즘 문제의 진정한 묘미는, 사람은 전체적인 상황을 한 번에 볼 수 있기 때문에 문제가 되지 않지만 컴퓨터의 경우 하나씩 봐야 하는 상황에서 어떻게 접근해야할지(컴퓨터에게 어떻게 상황을 알려줘야하는지)를 잘 찾아내는 것이다. 이 문제가 바로 접근법에 대해 고민해보기 좋은 문제라고 생각한다.

function trap(height: number[]): number {
    const rightMaxArr = Array.from({ length: height.length }, () => 0);

    let rightMax = 0;
    for (let i = height.length - 1; i >= 0; i--) {
        const target = height[i];

        if (target > rightMax) {
            rightMax = target
        }

        rightMaxArr[i] = rightMax
    }

    let leftMax = 0;
    let answer = 0;

    for (let i = 0; i < height.length; i++) {
        const target = height[i]
        rightMax = rightMaxArr[i]

        if (target > leftMax) {
            leftMax = target;
            continue;
        }

        if (target < leftMax && target < rightMax) {
            answer += Math.min(leftMax - target, rightMax - target)
        }
    }

    return answer;
};