[LeetCode] Trapping Rain Water 풀어보기

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

Trapping Rain Water - LeetCode

이전에 백준에 빗물트래핑? 이라는 비슷한 문제가 있었던거 같은데 이 문제에서 따왔나 싶네요

 

문제는 그래프의 높이에 따라 고일 수 있는 물의 넓이를 계산한 것입니다.

이 문제에서 핵심은 물의 넓이를 어떻게 계산할지입니다. 세로로 계산하는 것이 계산하기에는 가장 간단해보입니다.

 

무슨 말이냐면, 현재위치에서 왼쪽에 있는 bar중 가장 높은 높이, 오른쪽의 가장 높은 높이를 알고있다면 현재 위치에서의 세로 높이를 알 수 있다는 것입니다.

 

계산식은 area = min(leftmax, rightmax) - height[i] 정도가 될 것입니다.

class Solution {
public:
    int trap(vector<int>& height) {
        int N = height.size();
        vector<int> maxLeft(N, 0);
        vector<int> maxRight(N, 0);

        int leftMax = 0;
        int rightMax = 0;
        for (int i = 0; i < N-1; ++i)
        {
            leftMax = max(leftMax, height[i]);
            maxLeft[i + 1] = leftMax;
        }
        for (int i = N-1; i > 0; --i)
        {
            rightMax = max(rightMax, height[i]);
            maxRight[i - 1] = rightMax;
        }

        int answer = 0;
        for (int i = 0; i < N; ++i)
        {
            int area = min(maxLeft[i], maxRight[i]) - height[i];

            if (area > 0)
                answer += area;
        }

        return answer;
    }
};

---

막상생각해보면 배열도 필요없습니다. 

class Solution {
public:
    int trap(vector<int>& height) {
        int N = height.size();

        int left = 0;
        int right = N - 1;

        int leftMax = 0;
        int rightMax = 0;

        int answer = 0;

        while (left <= right)
        {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);

            if (leftMax <= rightMax)
            {
                answer += leftMax - height[left];
                ++left;
            }
            else
            {
                answer += rightMax - height[right];
                --right;
            }
        }

        return answer;
    }
};

왼쪽이 더 낮다면 왼쪽을 확정하고 오른쪽이 더 낮다면 오른쪽을 확정해나가며 이어나가면 되겠습니