[DSA][Two Pointers] 05. Trapping Rain Water

LeetCode 42

 

05. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1,
compute how much water it can trap after raining.

 

 

[질문하기]

- 양 끝은 bound 되지 않았다고 가정하나요? YES

- 모든 height 값은 양의 정수인가요, 0도 포함되나요? 0을 포함한 자연수 값이 가능하다.

 

 

[아이디어]

- 각 인덱스에 대해 왼쪽과 오른쪽에서의 max bar의 높이를 구하자.

 

 

[풀이 1] Prefix & Suffix Arrays

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        maxL = [0] * n
        maxR = [0] * n

        for i in range(1, n):
            maxL[i] = max(maxL[i - 1], height[i - 1])
            maxR[n - i - 1] = max(maxR[n - i], height[n - i])

        res = 0
        for i in range(n):
            res += max((min(maxL[i], maxR[i]) - height[i]), 0)
        
        return res

예시를 바탕으로 담을 수 있는 물의 양을 계산하다 보면, 아래의 사고의 흐름이 생긴다.

1) 양 옆의 bar가 나보다 높아야 물을 담을 수 있다.

2) 두 bar 중 낮은 bar로 담을 수 있는 물의 양이 정해진다.

3) 바로 옆이 아니라 조금 떨어진 bar라도 높이가 옆의 bar들보다 더 높으면 해당 bar로 인해 담을 수 있는 물이 생긴다.

위의 세 가지 사실로부터 인덱스 i에서 담을 수 있는 물의 양은 i보다 왼쪽에 있는 bar 중 가장 높은 bar, 오른쪽에 있는 bar 중 가장 높은 bar 두 개로 결정되며, 둘 중 더 작은 높이의 bar와 i에서의 높이차만큼 물을 담을 수 있다는 수식을 도출할 수 있다.

 

따라서 인덱스 i 기준 i보다 왼쪽에서 가장 큰 값을 저장하는 maxL 배열과 오른쪽에서 가장 큰 값을 저장하는 maxR 배열을 만든 후 두 값 중 작은 값과 높이 차로부터 물의 양을 계산할 수 있다.

 

⏱️ 시간복잡도

배열을 한 번 순회하기 때문에 O(n)의 시간 복잡도를 갖는다.

🧠 공간복잡도

maxL과 maxR 배열이 필요하므로 O(n)의 공간 복잡도를 갖는다.

 

 

[풀이 2] Two Pointer

class Solution:
    def trap(self, height: List[int]) -> int:
        L, R = 0, len(height) - 1
        maxL, maxR, res = 0, 0, 0

        while L < R:
            if height[L] < height[R]:
                if height[L] < maxL:
                    res += maxL - height[L]
                else:
                    maxL = height[L]
                L += 1
            else:
                if height[R] < maxR:
                    res += maxR - height[R]
                else:
                    maxR = height[R]
                R -= 1
        
        return res

 

Two Pointer를 사용하되 작은 쪽 포인터를 먼저 움직이며 물의 양을 계산하면 추가 배열 없이도 좌우 최대 높이를 실시간으로 추적할 수 있다.

 

그런데 왜 항상 작은 쪽 포인터를 먼저 움직일까?

한 방향에서만 살펴보면, maxL < maxR일 때 왼쪽 위치 L에서 고일 수 있는 물의 양은 min(maxL, maxR) - height[L]이 된다.
이 경우 min(maxL, maxR) == maxL이므로, 물의 양은 maxL - height[L]로 계산할 수 있다.

또한 이 시점에서 L 위치에서의 최종 maxR 값을 정확히 모르더라도, maxR은 오른쪽으로 이동하면서 계속 더 큰 값으로 갱신되기 때문에 지금보다 더 작아지는 일은 없다. 즉, "나중에 maxR이 줄어들어서 maxL > maxR이 되는 거 아니야?"라는 걱정은 할 필요가 없다.

따라서 maxL < maxR일 때는 왼쪽 값을 신뢰하고 계산해도 안전하며, 반대로 maxL > maxR일 때는 오른쪽 값을 먼저 계산하면 된다.

⏱️ 시간복잡도

배열을 한 번 순회하기 때문에 O(n)의 시간 복잡도를 갖는다.

🧠 공간복잡도

두 포인터와 각 방향에서의 max 값에 대한 변수만 필요하므로 O(1)의 공간 복잡도를 갖는다.