[leetcode] 42. Trapping Rain Water

문제 설명

링크

물이 고일 수 있는 양 구하기
유사문제

접근 1 - Two pointers

• Container with most water문제와 유사하게 l, r pointer 2개를 두고, 양을 더하고 빼는 방식
• minHeight 를 계산해두고, 포인터 이동 이후 이동된 위치의 높이만큼 빼주기
• 이동된 위치에서 minHeight 를 갱신했을 때, 기존보다 크다면 res 값에 그 차이 넓이만큼 더해주기

코드 1

    def trap(self, height: List[int]) -> int:
        minH = res = 0
        l, r = 0, len(height) - 1
        
        while l < r:
            h = min(height[r], height[l])
            if h > minH:
                diff = h - minH
                res += (r - l - 1) * diff
                minH = h
             
            if height[l] <= height[r]:
                l += 1
                if l < r and minH > 0: res -= min(minH, height[l])
            else:
                r -= 1
                if l < r and minH > 0: res -= min(minH, height[r])

        return res

접근 2 - Two Pointers 2

• minHeight 대신 left, right max 값 두기
• leftMax 가 height[left] 보다 크면 차이값 더하고 작으면 갱신
• 접근 1보다 조금 빠름

코드 2

    def trap(self, height: List[int]) -> int:
        minH = res = 0
        l, r = 0, len(height) - 1
        leftMax = rightMax = 0
        
        while l < r:             
            if height[l] <= height[r]:
                if height[l] >= leftMax:
                    leftMax = height[l]
                else:
                    res += (leftMax - height[l])
                l += 1
                
            else:
                if height[r] >= rightMax:
                    rightMax = height[r]
                else:
                    res += (rightMax - height[r])
                r -= 1
                
        return res

접근 3 - DP

• 각 위치마다 left max, right max 를 구한다. (각 위치에 담길 수 있는 물의 높이를 구하는 것임)
• ans += min(left max, right max) - height

    def trap(self, height: List[int]) -> int:
        if height == []:
            return 0

        n = len(height)
        max_left = [0]* n
        max_right = [0]* n

        max_left[0] = height[0]
        max_right[-1] = height[-1]
        for i in range (1, n):
            max_left[i] = max(max_left[i - 1], height[i])
             
        for i in range(n-2, -1, -1):
            max_right[i] = max(max_right[i + 1], height[i])

        output = 0

        for i in range(n):
            lower_boundary = min(max_left[i], max_right[i])
            max_trap_at_i = lower_boundary - height[i]
 
            output += max_trap_at_i
                
        return output