[LeetCode 42] Trapping Rain Water (Java)

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

---

풀이

이 문제는 각 막대의 너비가 1인 고도지도에서 높이를 나타내는 음수가 아닌 정수 n들이 주어질 때, 얼마나 많은 물이 비가 온 뒤 갇히는지 계산하는 문제이다.

1. 투포인터

물이 갇히려면 어떤 조건이 필요할까? 바로, 양쪽에 벽이 있어야한다.
즉, 가운데보다 더 높이가 높은 칸이 왼쪽과 오른쪽에 존재해야 물을 가둘 수 있는 것이다.

이제 무엇이 벽이 될 수 있는지를 알아보자.
왼쪽과 오른쪽에서 가운데로 이동하다보면, 벽 역할을 하는 것은 왼쪽과 오른쪽의 최대값들이다.

다음의 예시를 보며 이해해보자.
[1, 0, 1, 3, 1, 2]에서, 최초에는 벽 역할을 하는 것은 시작과 끝 원소인 1과 2이다. 따라서, 이 중 더 낮은 값인 1로 물을 가두게 될 것이다.

즉, [1, 1, 1, 3, 1, 2]가 된다는 의미다.

다음으로, 더 낮은 벽이었던 왼쪽 벽을 이동시키다보면, 왼쪽 벽이 3이 될 것이다. 왼쪽 벽이 3, 오른쪽 벽이 2이므로 더 낮은 값인 2로 물을 가두게 될 것이다.

따라서, [1, 1, 1, 3, 2, 2]가 될 것이다.

다음으로, 더 낮은 벽이었던 오른쪽 벽을 이동시키다보면, 왼쪽 벽과 만나게 될 것이고, 이 때 프로그램을 종료하면 된다.

이 예시를 통해, 벽 역할을 하는 것은 왼쪽과 오른쪽에서의 최대값들이고, 이 둘 중 최소값으로 물을 가두게 된다는 것을 알 수 있다.

따라서, 이 문제는 투포인터로 왼쪽과 오른쪽을 가리키게 하여 문제를 해결할 수 있을 것이다.

이를 코드로 옮기면 다음과 같다.

class Solution {
    public int trap(int[] height) {
        int left = 0, leftMax = height[left];
        int right = height.length - 1, rightMax = height[right];
        int waters = 0;

        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            int target = Math.min(leftMax, rightMax);
            if (leftMax <= rightMax) {
                waters += target - height[left];
                left++;
            } else {
                waters += target - height[right];
                right--;
            }
        }

        return waters;
    }
}

2. 스택

이 문제는 monotone-stack으로도 해결할 수 있다.

스택에 내림차순으로 원소를 저장하도록 하면, 현재 값이 top보다 큰 값이 오게 되면 top의 다음 값과 현재 값을 벽으로 설정하여 물을 가둔다고 이해하면 된다.

하지만, 이 경우에는 거리를 계산할 수 있어야하기 때문에, 스택에 인덱스를 저장해야한다.

따라서, 스택이 monotone을 유지하도록 하는 조건은 height[i] > height[stack.peek()]이 될 것이다.

곧바로, stack.pop()을 진행하여 top을 구한뒤, 스택이 비어있다면 루프를 탈출하고, 그렇지 않다면 계속 루프를 돌게하면 된다.

그리고, 거리는 i - stack.peek() - 1이 될 것이며, 수위는 Math.min(height[i], height[stack.peek()]으로 설정될 것이다. 이 경우, 갇히는 물의 양은 (i - stack.peek() - 1) * (Math.min(height[i], height[stack.peek()]) - height[top])가 된다.

이를 코드로 옮기면 다음과 같다.

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int volume = 0;

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                Integer top = stack.pop();
                
                if (stack.isEmpty())
                    break;
                
                int distance = i - stack.peek() - 1;
                int level = Math.min(height[i], height[stack.peek()]);
                volume += distance * (level - height[top]);
            }

            stack.push(i);
        }

        return volume;
    }
}