42. Trapping Rain Water

height = [0,1,0,2,1,0,1,3,2,1,2,1]

class Solution:
    def trap(self, height):
        stack = []
        sum = 0

        for i in range(len(height)):
            # 우측 벽 찾으면 벽 사이의 물 다 빼줌.
            while stack and height[i] > height[stack[-1]]:
                # 벽을 찾았으니 물을 계산할 칸인 스택 탑을 빼줌.
                top = stack.pop()

                # 팝했는데 스택이 비었으면 왼쪽에 벽이 없는거니 고여있는 물도 없는거임.
                if not len(stack):
                    break

                # 가운데 물의 길이를 구함
                distance = i - stack[-1] - 1
                # 왼쪽벽 높이, 우측 벽 높이 중에 작은 값에 물이 있던 칸의 높이를 빼줘야 해당 칸의 물 높이임.
                water = min(height[i], height[stack[-1]]) - height[top]
                # 구한 물 높이에 거리를 곱해줌.
                sum += distance * water

            # 스택에 추가
            stack.append(i)
        return sum


print(Solution.trap(Solution, height))

문제