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