LeetCode 42번 Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

---

문제 파악

여러 개의 음이 아닌 정수들로 이루어진 배열이 주어지는데, 이 배열은 각 정수가 가로 너비가 1인 막대기의 높이를 나타내는 지도이다. 비가 온 후 이 막대기들 사이에 고일 수 있는 물의 양을 계산해야 한다.

좀 더 구체적으로 설명하면:

1. 각 막대기는 고정된 너비(1)를 가지고 있으며, 배열의 각 원소는 막대기의 높이를 나타낸다.
2. 배열의 각 위치에서 고일 수 있는 물의 양을 계산해야 한다.
3. 물은 막대기 사이의 빈 공간에 고이며, 양 옆에 더 높은 막대기가 있을 때 물이 고인다.

접근 방법

1. 배열의 왼쪽 끝과 오른쪽 끝에서 각각 포인터를 하나씩 둔다.
2. 각 포인터에서 높이 값을 비교하면서 더 낮은 쪽의 포인터를 움직인다.
3. 포인터를 움직일 때, 현재 높이와 포인터가 움직이는 쪽의 최대 높이 값 사이의 차이만큼 물이 고인다고 계산한다.
4. 이 과정을 배열의 중간에서 두 포인터가 만날 때까지 반복한다.

코드 구현

class Solution:
    def trap(self, height: List[int]) -> int:
        # 투 포인터 사용을 위해 왼쪽, 오른쪽 지정
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        water_trapped = 0

        # 각 포인터에서 높이 값을 비교하면서 더 낮은 쪽의 포인터를 움직인다.
        while left < right:
            if left_max < right_max:
                left = left + 1
                left_max = max(left_max, height[left])

                # 현재 높이와 포인터가 움직이는 쪽의 최대 높이 값 사이의 차이만큼 물이 고인다고 계산
                water_trapped += left_max - height[left]
            else:
                right = right - 1
                right_max = max(right_max, height[right])
                water_trapped += right_max - height[right]

        return water_trapped