42. Trapping Rain Water

문제링크: https://leetcode.com/problems/trapping-rain-water/

다시 투포인터 문제다.

hard라길래 조금 시간을 투자해서 풀어보았다.

class Solution:
    def trap(self, height: List[int]) -> int:
        end = 0
        result = 0
        for block in range(len(height)):
            if height[block] >= height[end]:
                for i in range(end+1, block):
                    print(height[end] - height[i])
                    result += (height[end] - height[i])
                end = block

        return result

첫 트라이는 이렇게 했는데, 당연히 잡지 못하는 곳이 발생한다.

계속 고민했지만, 투포인터를 이용한 풀이는 도저히 생각이 안나서, 검색을 좀 해봤다.

class Solution:
  def trap(self, height: List[int]) -> int:
      left = 0
      right = len(height) - 1

      volume = 0

      left_max = height[left]
      right_max = height[right]

      while left < right:

          left_max = max(left_max, height[left])
          right_max = max(right_max, height[right])

          if left_max <= right_max:
              volume += (left_max - height[left])
              left += 1

          else:
              volume += (right_max - height[right])
              right -= 1
      
      return volume

이건 확실히 한번에 내 머리에서 나올수 없음ㅋㅋㅋㅋㅋ

left_max와 right_max를 이용해서 큰쪽을 갱신하며 volume을 더해주는 방식인데,

이걸 처음 풀면 어케아냐고..ㅋㅋㅋㅋ