Today's Challenge

https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

물이 고이는 양을 구하는 문제.
단순하게 brute force를 사용하면 O(n^2)이라 TLE 걸림.
Solution을 봤더니 매우 쉬운 방법을 공개함.
1. 가장 높은 값을 구함
2. 가장 높은 값을 가진 위치를 기준으로 왼쪽과 오른쪽을 나눈 뒤에 고인물 더함.

class Solution:
    def trap(self, height: List[int]) -> int:
        h_len = len(height)
        
        b_left = [height[0]] * h_len
        b_right = [height[-1]] * h_len
        
        for i in range(1, h_len):
            b_left[i] = max(b_left[i-1], height[i])
            b_right[-i-1] = max(b_right[-i], height[-i-1])
        
        return sum(min(b_left[i], b_right[i]) - height[i] for i in range(h_len))