[LeetCode # 42] Trapping Rain Water

정수형 배열이 주어지고, 이 배열이 저장하고 있는 값이 해당 위치의 벽의 높이라고 했을 때, 빗물을 받을 수 있는 총량을 구하는 문제

 

이 문제는 Two Pointer 방식으로 문제를 해결할 수 있었는데, Left 와 Right 에 각각 인덱스 포인터를 두고 이를 이동하면서 문제를 풀이하는 방식이다. 인덱스 포인터를 이동하면서 Left 에서의 최대값과 Right 에서의 최대값을 각각 저장해 두고 현재 인덱스 위치가 이보다 값이 작을 경우 빗물을 받을 수 있게 된다.

 

예를 들어, 위의 그림에서 left 는 0부터 right 는 11부터 시작한다. left, right 인덱스 위치를 보고 높이가 낮은 쪽을 우선한다.

현재 left 인덱스가 1인 경우, left max (0) 보다 현재 높이가 높으므로 left max 를 갱신한다. 그 다음 left 가 2가 되었을 때, 현재 높이보다 left max 가 크므로 left max 와 현재 높이의 차이만큼 물을 받을 수 있게 된다.

 

이러한 방식으로 left 와 right 포인터를 각각 이동하며 빗물을 받는 양을 구할 수 있다. 이러한 풀이로 작성한 코드는 다음과 같다.

 

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, left_max = 0, right_max = 0;
        int left, right;
        for (left = 0, right = height.size() - 1; left < right; ) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                }
                else {
                    ans += left_max - height[left];
                }
                left++;
            }
            else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                }
                else {
                    ans += right_max - height[right];
                }
                right--;
            }
        }
        return ans;
    }
};