빗물 트래킹 문제

height 라는 높이가 주어질 떄, 아래의 그림의 까만색 막대에 해당된다. 비가 온 후에 저렇게 물이 고일 때 쌓인 물의 면적의 합을 구하는 문제이다.

 

 

풀이 1) 투 포인터를 최대로 이동

가장 높이가 높은 막대를 살펴보자... 높이가 3인 것을 알 수 있다. 막대는 높고 낮음에 무관하게, 전체 부피에 영향을 끼치지 않으면서 그저 왼쪽과 오른쪽을 가르는 장벽 역할을 한다..

좌우 기둥 최대높이 left_max, right_max 라할 떄 이게 현재 높이와의 차이만큼 물 높이를 volume 에 더해준다. 

volume += left_max - height[left] 가 의미하는 것은 왼쪽 가장 높은 기둥에서 현재 기둥 높이를 뺀 값이다. 

left_max 가 2이고 height[left] 가 2이면 0으로 현재 기둥이 max 인 상태면 0을 뱉게 되고, left_max 가 2이고 height[left] 가 1이면 한칸 비니까 water 가 한칸 찰 수 있다고 본다.

 

 

    def trap(self, height: List[int]) -> int:
        if not height:
            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

 

 

 

풀이 2) 스택 쌓기

코드에 stack 리스트가 있는데, 여기에 들어가는 것은 변곡점 앞까지의 인덱스들이다. 아래의 그림에서 변곡점을 표시하였는데 기존의 기둥보다 더 높은 기둥을 만났을 때를 변곡점이라 한다. 

더 높은 변곡점을 만났으니 이전 변곡점 다음부터 현재 변곡점 전까지 쌓은 stack 을 하나씩 꺼내면서 인덱스에 해당하는 값을 가져와서 채워진 물의 양을 계산한다..

    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
                    
                # 이전과의 차이만큼 물 높이 처리
                disance = i - stack[-1] - 1
                waters = min(height[i], height[stack[-1]]) - height[top]
                
                volume += distance * waters
            stack.append(i)
        return volume