[LeetCode]빗물 트래핑

문제

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라

• Example 1:
  

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

• Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

코드

class Solution {
public:
    int trap(vector<int>& height) {
        
    vector<int>::iterator left = height.begin();
    vector<int>::iterator right = height.end() - 1;

    int volume = 0;
    int leftHeight = *(left);
    int rightHeight = *(right);

    while (left != right)
    {
        if (leftHeight <= rightHeight)
        {
            left++;
            if (leftHeight <= *(left)) leftHeight = *(left);
            if (leftHeight > *(left)) volume += leftHeight - *(left);
        }
        else if (leftHeight >= rightHeight)
        {
            right--;
            if (rightHeight <= *(right)) rightHeight = *(right);
            if (rightHeight > *(right)) volume += rightHeight - *(right);
        }
    }
    return volume;
    }
};

풀이

• 투 포인터 방식을 이용. 양쪽 기둥의 크기가 같거나, 한쪽이 더 커야 빗물이 저장되기 때문에
  양쪽 크기를 비교하며 계산을 한다.
• 왼쪽 오른쪽의 각각 최대 크기를 갱신해가며 포인터를 이동 시키는데, 이동하면서 현재의 최대길이 값보다 현재의 값이 낮다면 그 차이 만큼 계산하여 volume의 더 해준다.

결과

Runtime 11 ms / Memory 19.7 MB
https://leetcode.com/problems/trapping-rain-water/submissions/880025942/

---

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