42. 빗물 트래핑

빗물 트래핑
Hard
파이썬 알고리즘 인터뷰 180p

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

♬idea

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: #리스트가 empty인지 확인
            return 0
        
        # 변수 선언
        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        
        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
            
            # 더 높은 쪽을 향해 투 포인터 이동
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
                
            else:
                volume += right_max - height[right]
                right -= 1
                
        return volume

두 포인터를 중앙으로 움직이면서 받아지는 물의 양을 계산하는 방법이다.

 

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        volume = 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
                waters = min(height[i], height[stack[-1]]) - height[top]
                
                volume += distance * waters
                
            stack.append(i)
        return volume