[ LeetCode - 42 ] Trapping Rain Water

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

Trapping Rain Water - LeetCode

스택으려 풀려다가 시간이 너무 오래 걸렸어가지고 다 못풀고 투 포인터 방법을 찾아서 풀게 되었다.

스택으로 충분히 풀 수 있을거 같은데 나는 그림으로 그렸을 때 나오는 패턴 한개가 처리가 안되서 다 카운트가 되지 않았다..ㅠ

---

[ 📌 풀이 ]

1) 왼쪽, 오른쪽에 대해서 left, right 인덱스와 left, right에서 가장 높은 기둥의 height를 저장해둔다. (물이 갇히는 기준은 높은 기둥이니까 기억 해두었다가 낮은 기둥을 지날 때 카운트 해줘야 한다.)

 

2) left와 right의 기둥의 height가 더 낮은 쪽이 중앙으로 이동한다.

 

3) 이동 시 가지고 있던 기둥의 최대 height 보다 이동하는 지점의 기둥 height 가 높다면 갱신한다.

 

4) 높은 기둥 기준으로 갇힌 물 카운팅

 

 

while문이 돌면서 변경되는 값을 시각화 해서 그려놓은 그림이다.

---

[ 📌 코드 - Python ]

class Solution:
    def trap(self, height: list[int]) -> int:
        ans, left, right = 0, 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        
        while left < right:
            if left_max <= right_max:
                left += 1
                left_max = max(left_max, height[left])
                ans += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                ans += right_max - height[right]
                
        return ans

---

[ 📌 결과 ]

[ Result ]

[ 📌 노력 ]

[ 하찮은 나의 노력 ]