Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

My code

class Solution:
    def trap(self, height: List[int]) -> int:
        result = 0
        L = 0
        R = len(height)-1
        L_max = 0
        R_max =0
        while L<R:
            if height[L]<height[R]:
                if height[L]>=L_max:
                    L_max = height[L]
                else:
                    result += L_max - height[L]
                L+=1
            else:
                if height[R] >=R_max:
                    R_max = height[R]
                    
                else:
                    result+= R_max - height[R]
                R-=1
        return result
                        

Review

[실행 결과]
Runtime: 84 ms / Memory: 15.5MB

[접근법]
가장 높은 벽을 기준으로 얼만큼 낮아져있는지 계산해야 하기 때문에, 가장 높은 벽을 찾은 후, 만약 해당 벽이 가장 높은 벽보다 작으면 차이(물 들어갈 크기)를 result값에 저장한다. 만약 가장 높은 벽보다 더 높으면 높은 벽 값에 저장한다.
1번을 왼쪽 벽이 높을 때, 오른쪽 벽이 높을 때를 기준으로 나눠서 실행한다.

[느낀점]
무지성으로 끝을 기준으로 처음부터 차례차례 계산했더니 안됐다.
어제와 마찬가지로 양쪽 방향으로 생각하는 방법을 기억하자.....