비가 온 후 물이 갇히는 양 계산하기 - 42. Trapping Rain Water

너비가 1인 막대로 이루어진 고도 지도를 나타내는 n개의 음이 아닌 정수가 주어졌을 때, 비가 내린 후 갇힐 수 있는 물의 양을 계산하세요.

예시 1:

입력: height = [0,1,0,2,1,0,1,3,2,1,2,1]

출력: 6

설명: 위의 고도 지도(검은색 부분)는 배열 [0,1,0,2,1,0,1,3,2,1,2,1]로 나타낼 수 있습니다.

이 경우, 6 단위의 빗물(파란색 부분)이 갇히게 됩니다.

예시 2:

 

입력: height = [4,2,0,3,2,5]

출력: 9

제약 조건:

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

 

풀이

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        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 += 1
                left_max = max(left_max, height[left])
                water_trapped += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                water_trapped += right_max - height[right]

        return water_trapped

 

• left와 right 포인터는 각각 배열의 시작과 끝에서 시작합니다.
• left_max와 right_max는 현재까지의 왼쪽 및 오른쪽에서 가장 높은 막대의 높이를 기록합니다.
• 만약 left_max가 right_max보다 작다면, 왼쪽 포인터를 오른쪽으로 이동시키면서 물이 갇힐 수 있는 높이를 계산하고, 그 값을 water_trapped에 더합니다.
• 반대로 right_max가 더 크다면, 오른쪽 포인터를 왼쪽으로 이동시키면서 물이 갇힐 수 있는 높이를 계산합니다.
• 결국, 두 포인터가 만날 때까지 이 과정을 반복하고, 최종적으로 갇힌 물의 총량을 반환합니다.