[파이썬 알고리즘] 7장 배열 - 빗물 트래핑 (trapping rain water)

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

Trapping Rain Water - LeetCode

 

<문제>

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.

 

<예시>

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.

 

 

---

나만의 풀이를 못 찾았던 문제 ...

문제를 어떻게 해결해야 할 지 생각하는 연습을 더 많이 해야할 것 같다 

 

책에서는 two-pointer를 활용하여 풀이를 하였는데,

단방향으로는 풀 수 없고, 양쪽 방향에서 최대 높이를 향해 비어있는 공간을 채우는 식으로 계산해야 한다.

 

def solution1(height: List[int]) -> int:
    if height == []:
        return 0
    else:
        water = 0
        left_pointer = 0
        right_pointer = len(height)-1
        left_max, right_max = height[left_pointer], height[right_pointer]

        # index가 check해야 "할" 위치를 가리키므로
        # left_pointer와 right_pointer가 같아도 실행해야 한다.
        while left_pointer <= right_pointer:
            if left_max <= right_max:
                # 왼쪽에서 오른쪽으로
                if height[left_pointer] > left_max:
                    left_max = height[left_pointer]
                else:
                    water += (left_max - height[left_pointer])
                left_pointer += 1 # 왼쪽에서 오른쪽으로 이동
            else:
                # 오른쪽에서 왼쪽으로
                if height[right_pointer] > right_max:
                    right_max = height[right_pointer]
                else:
                    water += (right_max - height[right_pointer])
                right_pointer -= 1 # 오른쪽에서 왼쪽으로 이동
        return water