greentea31's Note

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

풀이 과정

다음과 같은 input이 들어올 때, 고이는 물의 총부피를 구하는 문제이다.

가장 높은 바닥을 기준으로 왼쪽 영역과 오른쪽 영역으로 나눠서 생각하면 풀이 방법이 빠르게 떠오른다.

왼쪽 영역은 왼쪽에서부터, 오른쪽 영역은 오른쪽에서 부터 읽어 나가면서, 여태 나왔던 바닥의 최대 높이를 저장하고, 바닥의 최대 높이 - 현재 바닥의 높이만큼 물이 고일 것이므로 그만큼을 정답 변수에 더해주면 된다.

소스 코드

class Solution:
    def trap(self, height: List[int]) -> int:
        left_max, right_max = 0, 0
        max_height_index, max_height = 0, 0
        answer = 0
        
        for i in enumerate(height):
            if max_height < i[1]:
                max_height_index, max_height = i[0], i[1]
                
        for i in range(0, max_height_index):
            if left_max < height[i]:
                left_max = height[i]
            else:
                answer += left_max - height[i]
        
        for i in range(len(height)-1, max_height_index, -1):
            if right_max < height[i]:
                right_max = height[i]
            else:
                answer += right_max - height[i]
        
        return answer