'ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ ์ธํฐ๋ทฐ' ์ฑ ์ผ๋ก ์ฝ๋ฉํ ์คํธ ๊ณต๋ถํ๋ค๊ฐ ํ์ด๋ฅผ ๋ด๋ ์ดํด๊ฐ ๊ฐ์ง ์ํ๋ ๋ถ๋ถ์ด ์์ด ์ผ๋จ ๊ธฐ๋กํด๋๊ณ ๋์ค์ ๋ค์ ์ฐจ๊ทผ์ฐจ๊ทผ ์ดํดํ๋ ค๊ณ ๋จ๊ฒจ๋๊ธฐ!
์ด ๋ฐฉ๋ฒ ๋ค๋ฅธ ๋ธ๋ก๊ทธ ๊ธ์ ํตํด ์ดํด๊ฐ ๋์๋ค.
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
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
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]]: # 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