[파이썬 알고리즘 인터뷰] 8. 빗물 트래핑

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

8. 빗물 트래핑

리트코드 42번 문제입니다.

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

 

 

풀이

 hard 문제답게 손도 못대보았습니다.

 

 책에는 두 가지 풀이법이 제시되었습니다.

 

1. 투포인터를 활용한 풀이

 양쪽의 포인터가 제일 높은 높이를 향해서 한 칸씩 이동합니다.

 이동하면서 이전 값과 현재 값의 차이로 물의 양을 계산합니다.

 

def trap(self, height):
    if not height:
        return 0

    left, right = 0, len(height)-1
    left_max, right_max = height[left], height[right]
    volume = 0
    while left < right:
        left_max, right_max = max(left_max, height[left]), max(right_max, height[right])
        if height[left] <= height[right]:
            volume += left_max - height[left]
            left += 1
        else:
            volume += right_max - height[right]
            right -= 1
    return volume

 

2. 스택을 이용한 풀이

 스택을 이용해서도 풀 수 있었습니다.

 코드를 이해하는데 시간이 오래 걸렸습니다.

 

def trap(self, height):
    stack = []
    volume = 0
    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            if len(stack) == 0:
                break
            distance = i - stack[-1] - 1
            water = min(height[i], height[stack[-1]]) - height[top]
            volume += distance * water
        stack.append(i)
    return volume