내 풀이
def trap(height: List[int]) -> int:
height2 = height
stack = []
# 스택이 비어있는데 높이가 있는 벽을 만나면 인덱스를 저장하고,
# 스택 젤 위의 벽의 높이보다 높은 벽을 만나면 계속 팝하며 비워낸다?
water_sum = 0
for i in range(len(height2)):
if stack:
if height2[i] >= height2[stack[-1]]:
while len(stack)>=2 and height2[stack[-1]] < height2[i]:
stack.pop()
water_height = min(height2[stack[-1]], height2[i])
for k in range(stack[-1]+1, i):
water_sum += water_height - height2[k]
height2[k] = water_height
if height2[i] > height2[stack[-1]]:
stack.pop()
stack.append(i)
elif height2[i] < height2[stack[0]]:
stack.append(i)
#스택이 비었을 경우
else:
#높이가 1이상이면 왼쪽 끝 벽이 생긴거다
if height2[i]>=1:
stack.append(i)
# print(i, stack, water_sum)
return water_sum예전에 이렇게 풀었지만 새로 푸니 아예 풀지를 못했다.
책 풀이
def trap(height: List[int]) -> int:
stack = []
total = 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]
total += distance * waters
stack.append(i)
return total현재 높이가 이전 높이보다 높을 때, 격차만큼 물 높이를 채운다. 이전 높이는 들쑥날쑥하기 때문에, 변곡점을 만날때마다 스택에서 하나씩 꺼내면서 이;전과의 차이만큼 물 높이를 채워 나간다.
유사한 문제
실패한 내 풀이
def trap(height: List[int]) -> int:
stack = []
water_sum = 0
for i in range(len(height)):
if stack and height[stack[-1]] < height[i]:
print()
print("index", i)
print("stack", stack)
tmp_low_height = height[stack.pop()]
tmp_list = []
tmp_list.append(tmp_low_height)
print(f"tmp_low_height : {tmp_low_height}")
while stack and height[stack[-1]] < tmp_low_height:
tmp_list.append(stack.pop())
print("tmp_list", tmp_list)
if stack:
min_height = min(height[i], stack.pop())
print("min_height", min_height)
for k in range(len(tmp_list)):
print(min_height - height[tmp_list[k]])
water_sum += min_height - height[tmp_list[k]]
stack.append(i)
print("done")
return water_sum