(LeetCode)42. 빗물 트래핑

문제

Trapping Rain Water - LeetCode

아이디어

  • 투포인터를 이용해 가운데 가장높은 장벽까지 왼쪽과 오른쪽 포인터중 값이 낮은 포인터를 이동시킨다(같은경우 오른쪽을 이동)
  • 가장높은 장벽에서 두 포인터가 만나면 종료

코드

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 = max(height[left], left_max)
            right_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

배운점

  • n^2으로 무식하게 해결할 수도있지만 간단한 아이디어로 O(n)에 해결가능