[배열] 08 빗물 트래핑(Trapping Rain Water) ✔

<LeetCode 문제>

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

Trapping Rain Water - LeetCode

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

<풀이>

이 문제는 높이와 너비 모든 공간을 차례대로 모두 살펴보면 O(N²)에 풀이가 가능합니다.

 

그러나 시간복잡도가 너무 높기 때문에 투 포인터나 스택으로 O(N)에 풀이할 수 있습니다.

 

투 포인터를 통해 풀이한 코드는 다음과 같습니다. 최대 높이의 막대까지 각각 좌우 기둥 최대 높이 left_max, right_max가 현재 높이와의 차이만큼 물 높이 volume을 더해 나갑니다.

[투 포인터 이용한 풀이]

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 = max(left_max,height[left])
            right_max = max(right_max, height[right])
            
            #더 높은쪽을 향해 투 포인터 이동
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
                
        return volume

<학습내용>

1.

<학습이 필요한 내용>

1.

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/Python_Study/07_array/LC_42.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers, LeetCode problem solving by Python, C++