[leetcode] 42.Trapping Rain Water (백준 14719 빗물)

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

Trapping Rain Water - LeetCode

 

백준에도 빗물이라는 문제가 있는데 동일하다 

https://www.acmicpc.net/problem/14719

14719번: 빗물

이거 well-known 이라며 그래서 나도 전에 한번 풀었던 것 같은데 또 다시 푸니까 어렵다 ㅋㅋ

여러가지 풀이가 있지만, 투포인터 활용하는 방법으로 푸는게 좀 더 이해가 잘 되었다 

left, right 포인터를 각각 맨 끝에서부터 이동시키면서, max_left와 max_right 값을 찾고 현재 height[left], height[right]와의 높이 차이를 volume에 더해 나간다 
그림으로 생각하면 좀 이해가 된다 

그림에서 max_left는 현재 1이고, left 포인터가 가리키는 height는 0이다 

따라서 max_left - height[left] 는 지금까지 중에서의 최대 높이와 현재 가리키는 지점의 높이 차이를 의미하며 핑크색으로 칠해진 빗물이 쌓이는 volume에 대한 값을 구할 수 있다 

이를 반복하여 volume에 더해나간다 

class Solution:
    def trap(self, height: List[int]) -> int:
        left = 0 
        right = len(height) - 1
        max_left = height[left]
        max_right = height[right]
        volume = 0 
        while left < right:
            max_left = max(max_left, height[left])
            max_right = max(max_right, height[right])
            
            if max_left <= max_right:
                volume += max_left - height[left]
                left += 1
            else:
                volume += max_right - height[right]
                right -= 1
        return volume