파이썬 알고리즘 인터뷰 - 08. 빗물 트래핑

 

<--- 리트코드 42. Trapping Rain Water --->

# 문제: 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라.

 

입력

[0,1,0,2,1,0,1,3,2,1,2,1]

출력

6

 

 

# 풀이

1. 투 포인터를 최대로 이동

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

 

2. 스택 쌓기

def trap(height):
  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
 
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height))