(8)42. Trapping Rain Water

“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/trapping-rain-water/

주어진 정수 배열은 지면의 높이를 나타낸다. 비가 온 후 물이 쌓일 수 있는지 알아내는 문제.

이건 난이도가 hard다. 무식하게 푸는 방법조차 떠오르지 않는 문제다. 풀이를 봐도 이해가 안 가서 더 생각을 해봐야겠다.

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

        for i in range(len(height)):
            while stack and height[i] > height[stack[-1]]:
                top = stack.pop()
                
                if not len(stack):
                    break
                
                distance = i - stack[-1] - 1
                waters = min( height[i], height[stack[-1]] ) - height[top]

                volume += distance * waters
            
            stack.append(i)
        
        return volume

이쪽으로는 역시 트이지 않은 건지 아무리 생각해봐도 뾰족한 수가 떠오르지 않았다. 풀이를 보고도 바로 이해가 안 가서 손코딩..으로 변수를 하나 씩 적어가며 확인해보니 어떤 방식인지 겨우 이해가 갔다. 풀이를 이해만 한 수준이라서 내 방식대로 정리하기가 어렵다. 스택이라는 기본 자료구조를 활용할 줄 알아야 한다는 것이 이번 문제의 포인트라고 생각한다.