[LeetCode] 42. Trapping Rain Water [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀
문제 👉 <Trapping Rain Water - LeetCode>

1. 문제 (빗물 트래핑)

(출처)

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

2. 풀이

1. 
   

   (출처)

   위 그림처럼 최대 높이의 막대까지 각각 좌우 기둥 최대 높이와 현재 높이와의 차이만큼 물 높이를 더해 나간다.

2. 스택을 이용한 풀이

   

   (출처)

   위 그림처럼 높아질 경우 변경된 높이만큼 물을 추가한다.

3. 코드

• 투 포인터를 이용한 풀이

class Solution:
    def trap(self, height: List[int]) -> int:
        # 종료 조건
        if not height:
            return 0

        ret = 0
        left, right = 0, len(height)-1
        left_max, right_max = height[left], height[right]

        while left < right:
            left_max, right_max = max(left_max, height[left]), max(right_max, height[right])
            # 더 높은 쪽을 향해 투 포인터 이동
            if left_max < right_max:
                ret += left_max - height[left]
                left += 1
            else:
                ret += right_max - height[right]
                right -= 1

        return ret

• 스택를 이용한 풀이

class Solution:
    def trap(self, height: List[int]) -> int:
        st = []
        volume = 0

        for i in range(len(height)):
              # 막대 높이가 높아질 경우
            while st and height[i] > height[st[-1]]:
                top = st.pop()

                if not len(st):
                    break

                distance = i - st[-1] - 1
                # 새로운 막대와 이전의 막대 중 낮은 막대만큼 물을 채운다
                waters = min(height[i], height[st[-1]]) - height[top]

                volume += distance * waters

            st.append(i)

        return volume 

• 결과 :

Time Submitted	Status	Runtime	Memory	Language
투포인터	[Accepted]	56 ms	14.9 MB	python3
스택	[Accepted]	56 ms	14.9 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋