[ Leetcode ] Trapping Rain Water

Problem)

 

Solution)

이전에 풀었던 "Container With Most Water"와 거의 유사한 문제입니다. 길이 n의 배열이 주어지고 배열의 각 값은 위 그림에 보이는 것 같이 'bar'의 길이를 나타냅니다. 이때, 비가 와서 물이 가득 찼을 때의 물의 양을 구하면 됩니다.

 

풀이법은 n 길이의 배열을 for loop으로 돌리면서 각 단계마다 중심 기둥이 되는 위치의 좌측에서 가장 높은 기둥을 "left", 그리고 우측에서 가장 높은 기둥 "right"라고 정의 합니다. 이때, left와 right중 작은 기둥의 높이 만큼 빗물이 찰 수 있게 되고 따라서 얻은 작은 기둥의 높이에서 중심 기중의 높이의 차이가 실제로 해당 공간에 빗물이 찰 수 있는 공간이 됩니다.

 

설명이 조금 복잡해 보이는데 아래 python code를 보시면 더욱 쉽게 이해되실 것 같습니다.

 

(1)

class Solution:
    def trap(self, height: List[int]) -> int:
        if height:
            water = 0
            
            for i in range(1, len(height) - 1):
                left = max(height[:i])
                right = max(height[i+1:])
                min_bar = min(left, right)
                
                if min_bar > height[i]:
                    water += min_bar - height[i]
            return water
        else:
            return 0

 

위의 솔루션 (1)에서 시간 복잡도를 신경써서 아래와 같은 코드를 완성할 수 있습니다.

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