7장_8 배열(빗물 트래핑)

1. 투포인터를 최대로 이용

from typing import List


class Solution:
    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

문제의 그림에서는 최대 높이가 3이다. 높이가 더 높아도 상관은 없지만 최대 높이까지 각각 좌우 기둥을 최대높이 left_max, right_max가 현재 높이와의 차이만큼 물높이 volume을 더해나간다.
낮은 쪽은 항상 물이 채워질 것이고 좌,우 끝에서 가장 높은 기둥까지 점점 물을 채우며 이동할 것이다. 그리고 마지막 최대 높이에서 좌우 포인터가 만나게 되며 끝난다.

2. 스택 쌓기

from typing import List


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

현재 높이가 이전 높이보다 높을 때 부분, 변곡점을 기준으로 스택에 쌓아 나가면서 격차만큼 물 높이 volume을 채운다. 높이가 계속 바뀌기 때문에 변곡점을 만날 때 마다 스택에서 하나씩 꺼내면서 이전과의 차이만큼 물 높이를 채워나간다. 라고 설명을 읽으며 이해는 했는데........ 다음에 이 문제가 나오면 스스로 설명을 하지 못 할 것 같다...스택 원리가 잘 이해가 되지 않았다...