[알고리즘][Python] LeetCode 42 Trapping Rain Water 문제 풀이

문제 출처 : leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

---

문제 해석 : 빗물이 고이는 총량을 계산하는 문제이다. 문제는 직관적이지만 다양한 접근을 활용할 수 있다.

 

문제 풀이 : 아래 풀이는 O(n^2)의 브루트포스 풀이법으로 각 원소마다 양쪽의 최댓값을 구해서 작은 부분과의 차를 전체 합에 더해 주는 방식이다. 하지만 이 풀이는 시간제한이 빡빡해 지면 통과하기 힘들다.

 

가능한 다른 풀이 : 다른 방법으로는 스택을 활용한 풀이, 투 포인터를 활용한 풀이 방법이 있다.

 

---

풀이 코드

from typing import List


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

        for i in range(1, len(height)-1):
            left_max = max(height[:i])
            middle = height[i]
            right_max = max(height[i+1:])
            if left_max > middle and right_max > middle:
                answer += min(left_max, right_max) - middle

        return answer

if __name__=="__main__":
    solution = Solution()
    height_in = [0,1,0,2,1,0,1,3,2,1,2,1]
    height_in2 = [4,2,0,3,2,5]
    print(solution.trap(height_in))
    print(solution.trap(height_in2))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 LeetCode 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.