빗물 트래핑(틀림)
풀이 방법
1. Stack 활용
class Solution:
def trap_stack(self, height_list: list[int]) -> int :
stack = []
vol = 0
for i in range(len(height_list)) :
while stack and height_list[i] > height_list[stack[-1]] :
top = stack.pop()
# 여기서 len(stack) == 0이 나오는 경우는 a, b가 연달아서 숫자가 높아졌을 때
# a를 append하고 바로 b가 나온다면 stack에서 top으로 pop 해주게 된다.
if len(stack) == 0 :
break
'''
stack에는 변곡점에 다다르지 않은 height_list에 대한 index들이 들어있고
stack[-1]은
변곡점을 만나기전 즉, 높은곳 >>> 낮은곳 >> 변곡점 >> 높은곳에서 낮은곳에 해당되는
것을 pop 해줬기 때문에 낮은곳에 나오기 전에 있던 첫 번째 높은 지점을 가르키고 있음
'''
distance = i - stack[-1] - 1
# height_list[top]은 사이에 있는 값이고
# height_list[i]와 height_list[stack[-1]]는 height_list[top]을 사이에 두고 있는 벽이다.
waters = min(height_list[i], height_list[stack[-1]]) - height_list[top]
vol += distance * waters
stack.append(i)
return vol
2. 투 포인터 활용
투 포인터의 해설은 Stack을 사용하는 것보다 간단하다.
max_left와 max_right이 있고 현재의 값이 min(max_right, max_left)보다 작으면 사잇값으로 치는거고 현재의 값을 min(max_left, max_right)에다가 빼면서 왼쪽 현재값이 오른쪽 현재값과 같아지면 함수가 종료되는 로직이다.
class Solution:
def trap(self, height: list[int]) -> int:
ans = 0
left = 0
right = len(height) - 1
max_left = max(left, height[left])
max_right = max(left, height[right])
while left < right :
max_left = max(height[left], max_left)
max_right = max(height[right], max_right)
if max_left <= max_right :
ans += max_left - height[left]
left += 1
else :
ans += max_right - height[right]
right -= 1
return ans