[LeetCode] 42. Trapping Rain Water

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

Stack

문제를 보고 valid parenthesis 같은 느낌이 나서 stack으로 풀어야겠다!

라고 접근했는데 대략적인 방법은 맞았지만 실제로 완전히 이해하고 구현하기까지 엄청 오래 걸렸던 문제다..🥲
엄청 헷갈려서 그냥 다 프린트를 찍어보고 나서야 좀 감이 왔다.

일단 스택으로 풀 때 중요한 것은

1) 내려갔다가 다시 올라올 때 물의 양을 계산하는 것
2) 물의 양은 왼쪽, 오른쪽 기둥 중 더 낮은 기둥을 기준으로 계산하는 것
이다.

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

        for i in range(len(height)):
            while stack and height[stack[-1]] < height[i]:
                last = stack.pop()

                if len(stack) == 0:
                    print("break here! stack is empty ", stack)
                    break

                # 왼쪽의 가장 높은 기둥
                left = stack[-1] 
                # 왼쪽과 오른쪽 사이의 너비
                width = i - left -1
                depth = min(height[i], height[left]) - height[last]

                water += depth * width
                print(f'   i : {i}, water : {water} , stack: {stack}, last: {last}, width: {width}, depth : {depth}')

            stack.append(i)
            print(f'i : {i}, water : {water} , stack: {stack}')



        return water

프린트 결과 값을 확인해보자.

# input : [0,1,0,2,1,0,0,1,1,3]

i : 0, water : 0 , stack: [0]
break here! stack is empty  []
i : 1, water : 0 , stack: [1]
i : 2, water : 0 , stack: [1, 2]
   i : 3, water : 1 , stack: [1], last: 2, width: 1, depth : 1
break here! stack is empty  []
i : 3, water : 1 , stack: [3]
i : 4, water : 1 , stack: [3, 4]
i : 5, water : 1 , stack: [3, 4, 5]
i : 6, water : 1 , stack: [3, 4, 5, 6]
   i : 7, water : 1 , stack: [3, 4, 5], last: 6, width: 1, depth : 0
   i : 7, water : 3 , stack: [3, 4], last: 5, width: 2, depth : 1
i : 7, water : 3 , stack: [3, 4, 7]
i : 8, water : 3 , stack: [3, 4, 7, 8]
   i : 9, water : 3 , stack: [3, 4, 7], last: 8, width: 1, depth : 0
   i : 9, water : 3 , stack: [3, 4], last: 7, width: 4, depth : 0
   i : 9, water : 8 , stack: [3], last: 4, width: 5, depth : 1
break here! stack is empty  []
i : 9, water : 8 , stack: [9]

우선 현재 기둥이 이전보다 더 높을 때 물의 양을 계산해야하고 (= 기둥높이가 내려갔다가 올라올 때), 이전 값이 있어야하기 때문에 while 문 조건은 비교적 직관적으로 찾을 수 있었다.

가장 헷갈렸던 것은 그러면 현재 기준 기둥이 아닌 왼쪽의 기둥 높이는 어떻게 구하지? 였다.

 

빠른 이해를 위해 그림을 보자..

6번-7번으로 넘어갈 때 물의 양이 한번 계산되고, 다시 8번에서 9번으로 넘어갈 때 한 번더 2층에 해당하는 물의 양이 계산된다.

 

프린트 문을 보면 stack중 pop 된 값을 제외한 마지막 값을 left로 쓰면 다시 올라가는 구간에서만 height가 인식되는 것을 볼 수 있다.

height에 변화가 생길 때만 depth에 값이 들어가는 것이다.

 

역시 헷갈릴 땐 프린트로 다 찍어보는게 좋은 것 같다..

Two Pointer

찾아보니 투 포인터로 푸는 방법이 좀 더 간결해 보인다.
왼쪽, 오른쪽에서 각각 출발해 더 높이가 낮은 쪽이 한칸씩 전진해서 가장 높은 기준점에서 만나는 방식이다.
가장 높은 점에서 만나는 것이 보장되어 있고, 둘 중 더 낮은 쪽이 이동하기 때문에 지나오는 깊이들을 모두 다 더할 수 있다.

각 포인터는 지나오면서 각자의 최고 높이 값과 현재 지나는 높이 값 만큼의 차이를 더하면 된다.

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

        left = 0
        right = len(height) -1

        left_max = height[left]
        right_max = height[right]

        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])
            if left_max < right_max:
                water += (left_max - height[left])
                left += 1
            else:
                water += (right_max - height[right])
                right -= 1
               
        return water