[LeetCode] C++ 42. Trapping Rain Water

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

문제

 

문제 분석

1. BruteForce로 검사하면 물론 답은 나오겠지만, 시간초과가 날 것입니다.

2. Two Pointer를 사용하는 방법. 물이 담기는 경우에는 항상 작은 것을 기준으로 담깁니다. 맨 왼쪽과 맨 오른쪽부터 시작하면서 가장 큰 블럭에 도달할 때까지 이동하면서 계산을 합니다. 가운데에 어떤 블럭이 있는지 모르는 상태에서 하나씩 접근해가면서 현재 왼쪽의 최댓값보다 오른쪽 블럭의 최댓값이 더 크다면 현재 위치에서 담길 수 있는 물의 양은 (왼쪽의 블럭 최댓값) - (왼쪽의 현재 위치의 블럭)이고, 왼쪽으로 포인터를 한 칸 이동시키면 됩니다. 오른쪽 관점도 마찬가지입니다.

3. 스택을 이용하는 방법. 물이 담기는 건 이전 블록보다 다음 블록이 높을 때, 즉 꺾이는 부분 변곡점을 기준으로 격차만큼 물 높이를 채웁니다. 계속 스택으로 채워나가다가 변곡점을 만날 때마다 스택에서 하나씩 꺼내면서 이전과의 차이만큼 물 높이를 채워 나가면 됩니다.

 

풀이 1 (Two Pointers)

#include <vector>
#include <algorithm>

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int left_max = height[left];
        int right_max = height[right];
        int volume = 0;

        while (left < right){
            left_max = max(height[left], left_max);
            right_max = max(height[right], right_max);
            
            if(left_max <= right_max){
                volume += left_max - height[left];
                left++;
            }else{
                volume += right_max - height[right];
                right--;
            }
        }

        return volume;

    }
};

 

풀이 2 (stack)

#include <vector>
#include <algorithm>
#include <stack>

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> stack;
        int volume = 0;

        for(int i = 0; i < height.size(); ++i){
            while (!stack.empty() && height[i] > height[stack.top()]){
                int top = stack.top();
                stack.pop();

                if (stack.empty())
                    break;
                
                int distance = i - stack.top() - 1;

                int waters = min(height[i], height[stack.top()]) - height[top];

                volume += distance * waters;
            }

            stack.push(i);
        }

        return volume;

    }
};