Trapping Rain Water

문제링크 : leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

블록의 높이를 배열로 받아 움푹 파이는 곳에 물이 받아진다는 설정이다. 결국 움푹 파인 공간을 세라는 문제.

책을 먼저 보고 다음날 머리에 넣기 위해 풀어보는 식으로 공부를 하고 있어서 왠지 안풀리겠다 싶은 부분은 계속 반복해서 보고 있다. 이 문제도 왠지 잊을 것 같아서 어제 달달 외우다시피 했더니 오늘 풀 수 있다.

중요한 포인트는 왼쪽과 오른쪽에서 포인터를 두고 한 번의 loop에서 가장 높은 곳을 향해 접근한다는 것 *과 *왼쪽이든 오른쪽이든 높은 벽에서 낮은 벽으로 이동하면 그만큼 움푹 파인것이라는 점이다.

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

        left, right = 0, len(height) - 1
        l_max, r_max = 0, 0
        result = 0
        while left != right:
            if l_max > height[left] or r_max > height[right]:
                result += l_max - height[left]
                result += r_max - height[right]
            else:
                l_max = height[left]
                r_max = height[right]

            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return result

책의 답은 나와 많이 다르다. 최대값은 if문 비교가 아니라 max()를 사용했고 높은 곳을 향하는 것도 내 경우 현재 값으로 비교했는데 최대값을 가지고 비교한다. (특히 최대값을 비교해서 이동하는 부분은 내가 잘못생각했다)

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

        left, right = 0, len(height) - 1
        l_max, r_max = height[left], height[right]
        result = 0
        while left < right:
            l_max, r_max = max(l_max, height[left]), max(r_max, height[right])
            if l_max <= r_max:
                result += l_max - height[left]
                left += 1
            else:
                result += r_max - height[right]
                right -= 1
        return result

오 그런데 내가 푼게 더 빠르고 메모리도 적게 먹었다 :) 아무래도 max 함수때문일거 같다.