알고리듬 : LeetCode 42. Trapping Rain Water

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하기

example input:
[0,1,0,2,1,0,1,3,2,1,2,1]

output:
6

풀이:

물의 높이를 구하려면 물이 언제 쌓이는지 생각해야한다.

현재 index에서의 물의 높이를 구해보자.

우선 현재 index 기준으로 왼쪽편에서 가장 높은 블럭과
오른쪽편에서 가장 높은 블록을 알아내야한다.
예를 들어, 현재 index의 블럭 높이가 1이고 왼쪽편 최고 높이 블럭이 2,
오른쪽편 최고 높이 블럭이 3이라고 하자.
물은 1부터 2 높이까지 1 블럭 쌓일 것이다. 그 이상의 물은 왼쪽편으로 흘러내려 쌓이지 못한다.

결국 현재 index에서 왼쪽과 오른쪽편의 서로 가장 높은 블럭을 비교하나 더 낮은 편의 블럭에
현재 index 블럭의 높이를 뺀 값이 현재 index의 물의 높이이다.

그리고 조건은 현재 index의 블록이 옆의 다른 블록보다 높으면 물이 쌓이지 않으므로 위의 뺄셈식에서 음수가 나오는 경우는 세지않는다.

높이를 나타내는 주어진 배열에 반복문을 한 번 사용하여 각 index에서의 물의 높이를 전부 더 한다.

class Solution:
    def trap(self, height: List[int]) -> int:

        unit = 0

        for i in range(1, len(height) - 1):
            volumes = min(max(height[:i]), max(height[i:])) - height[i]
            if volumes > 0:
                unit += volumes

        return unit

Thought:
Trapping Rain Water 라고 검색하면 이러한 유형의 문제가 나오는데, 표기된 난이도를 보면 전부 hard다.
위에 적은 풀이 코드는 짧고 간결하게 썼으나 문제에 써야하는 알고리듬 컨셉을 이해하는데 상당히 애를 먹었다.