[LeetCode] 42. Trapping Rain Water

투 포인터를 활용해 쉽게 풀이가 가능한 문제이다.

총 강수량을 축적해가며 물이 얼마나 고일 수 있는지 판단한다.

해당 방향의 가장 높은 벽 - 현재 벽의 높이 = 쌓일 강수량

위 공식을 그림을 통해 알기쉽게 표현되어있다.

😎풀이

function trap(height: number[]): number {
    if (height.length === 0) return 0;

    let left = 0; // 왼쪽 포인터
    let right = height.length - 1; // 오른쪽 포인터
    let leftMax = height[left]; // 왼쪽 최대 높이
    let rightMax = height[right]; // 오른쪽 최대 높이
    let waterTrapped = 0; // 고인 물의 양

    // 왼쪽 포인터가 오른쪽 포인터를 넘지 않을 때까지 반복
    while (left < right) {
        // 왼쪽 최대 높이가 오른쪽 최대 높이보다 작으면
        if (leftMax < rightMax) {
            left += 1; // 왼쪽 포인터를 이동
            leftMax = Math.max(leftMax, height[left]); // 새로운 왼쪽 최대 높이 갱신
            waterTrapped += leftMax - height[left]; // 현재 위치에서 고일 수 있는 물의 양을 추가
        } else {
            // 오른쪽 최대 높이가 더 크거나 같으면
            right -= 1; // 오른쪽 포인터를 이동
            rightMax = Math.max(rightMax, height[right]); // 새로운 오른쪽 최대 높이 갱신
            waterTrapped += rightMax - height[right]; // 현재 위치에서 고일 수 있는 물의 양을 추가
        }
    }

    return waterTrapped; // 최종적으로 고인 물의 양을 반환
}