[leetcode 매일풀기] 42 trapping rain water

오늘 리뷰할 문제는 trapping rain water이다.

 

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

Trapping Rain Water - LeetCode

 

문제로 말로 설명하자면, 2차원 세상에서 울퉁불퉁 솟아있는 기둥이 있고, 비가 충분이 온다고 가정했을 때. 기둥 사이에 고인 물의 양을 계산하는 문제이다.

 

검은색이 흙, 파란색이 물이라고 생각하면 된다.

 

물이 고이는 조건을 생각해보면, 현재 위치보다 왼쪽과 오른쪽 모두에 더 높은 기둥이 있으면 되고. 왼쪽 높은 기둥과, 오른쪽 높은 기둥중에 더 낮은 수치와, 현재위치의 높이의 차를 다 더하면 되겠다고 생각했다.

 

그래서 각 위치별로 왼쪽 기둥의 높이와, 오른쪽 기둥의 위치를 계산해서 저장하는 작업을 한 코드는 아래와 같다.

 

class Solution:
    def trap(self, height: List[int]) -> int:
        l_max = 0
        r_max = 0
        ls = []
        rs = []
        for h in height:
            if h > l_max:
                l_max = h
            ls.append(l_max)
        for h in height[::-1]:
            if h > r_max:
                r_max = h
            rs.append(r_max)
        rs = rs[::-1]

        res = 0
        for l, r, h in zip(ls, rs, height):
            res += min(l, r) - h
        return res

 

이렇게 제출하고 나면, leetcode에서 아래와 같은 결과창을 볼 수 있다.

첫번째 코드 결과창

 

leetcode를 꾸준히 풀다보니 대충 보는 요령이 생기는데, 저렇게 생긴걸 보면. 알고리즘의 time complexity자체에는 문제가 없는 것 같다.

다만 memory측면에서 더 개선할 방법이 있다고 판단해서, 다른사람들의 코드를 살펴보았다.

 

확인해보니, 왼쪽과 오른쪽 높은 기둥을 다 저장하지 않고, 순회를 하면서 할 수 O(1)의 공간을 사용해서 순회할 수 있는 알고리즘을 보고 구현해보았다.

from typing import List


class Solution:

    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        water = 0
        while left < right:
            if height[left] < height[right]:
                if height[left] > left_max:
                    left_max = height[left]
                else:
                    water += left_max - height[left]
                left += 1
            else:
                if height[right] > right_max:
                    right_max = height[right]
                else:
                    water += right_max - height[right]
                right -= 1
        return water


assert Solution().trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert Solution().trap([4, 2, 0, 3, 2, 5]) == 9

 

양옆에서부터 조여가면서 천천히 안에 들어가는 water를 채워나가는 식이고.

 

이번에는 잘 풀었다고 생각했는데, 항상 더 나은 솔루션이 있다는걸 leetcode를 보면서 배우는 것 같다.

코드를 짤 때 리뷰를 쓰지 않으니 뭔가 막연한 자신감이 생겼었는데, 더 좋은 해결책들을 보면서 겸손해야 함을 다시금 느끼게 되는 것 같다.