[LeetCode 42][Hard] Trapping Rain Water 파이썬 풀이

 

Problem

 

브루탈 포스 방식 O(N^2) 으로 접근하면 시간초과가 난다. O(n)으로 풀어야 하며 이를 위해 투포인터를 이용해야 한다.

 

문제 풀이

(1) 물의 부피 = 기둥의 최댓값 - 현재 기둥의 높이 로 직관적으로 알 수 있다.

(2) 기둥의 최댓값이 어느 범위에 존재할 수 있기에, 왼쪽 기준으로 최대 기둥 높이로 접근 // 오른쪽 기준으로 최대 기둥 높이로 접근하는 방식으로 생각해야 한다.

(3) 이를 위해 투포인터를 이용해서 풀이하면 O(N)으로 풀이가 가능하다.

 

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        w_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:
                w_volume += left_max - height[left]
                left += 1
            
            else:
                w_volume += right_max - height[right]
                right -= 1
        
        return w_volume