[LeetCode][C++/Python] 42번: Trapping Rain Water (261)

 

생각의 흐름

1. Stack을 활용한 풀이

처음 떠오른 방식은 Stack을 사용하는 방식이었다. (뭔가 예전에 풀어본건가? 그냥 보자마자 Stack부터 떠올랐다)

 

Stack에 게속 index를 추가하면서, 현재를 기점으로 이전보다 높이가 더 높은 경우에 해당 volume을 계산하여 결과변수에 더해준다.

글만 보면 이해가 안갈 수 있다, 다음 그림을 살펴보자.

우선 맨처음 1번 블록을 보면, 인덱스 2에서 3으로 넘어갈때 이전보다 높이가 높아지는 곳 이다. (0에서 2로)

따라서 다음 while문의 height[i] > height[stack.top()]을 만족시키게 된다.

while (!height_stack.empty() && height[i] > height[height_stack.top()]) {
    int top = height_stack.top();
    height_stack.pop();

    if (height_stack.empty()) {
        break;
    }

    int distance = i - height_stack.top() - 1;
    int h = min(height[i], height[height_stack.top()]) - height[top];
    res += (distance * h);
}

height_stack.push(i);

그럼 top의 값은 2가(index값) 나오게 되고,

distance는 3 - 1 - 1 로 1이 되고, distance == 1

h는 min(2, 1) - 0 으로 1이 된다. h == 1

따라서 더해줘야 할 volume은 1이 된다.

 

나머지 2번과 3번도 동일하게 계산하여 더해진다.

index 5에서 6으로 넘어갈 때 높이가 1, 거리가 1 따라서 volume 1이 더해지고,

index 6에서 7로 넘어갈 때도 높이가 높아진다. 따라서 높이는 1, 거리는 3으로 volume 3이 더해진다.

 

총합 6이 나오게 된다.

 

Two Pointer 풀이

투포인터 방식은 나는 생각하지 못한 방식이다.

 

이 방식은 그림상에서 가장 높이가 높은 지점을 중심으로, 왼쪽끝과 오른쪽 끝에서부터 중심을 향해 나아가는 방식이다.

max 높이보다 큰 높이를 만나게 되면 -> max높이를 갱신

max 높이보다 작거나 같은 높이를 만나게 되면 -> volume을 구해서 더해나간다!

 

 

나의 코드

1. C++

#include <bits/stdc++.h>

using namespace std;

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

        stack<int> height_stack;

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

                if (height_stack.empty()) {
                    break;
                }

                int distance = i - height_stack.top() - 1;
                int h = min(height[i], height[height_stack.top()]) - height[top];
                res += (distance * h);
            }

            height_stack.push(i);
        }

        return res;
    }
};

 

2. Python

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        res = 0
        left, right = 0, len(height) - 1
        l_max, r_max = height[left], height[right]

        while left < right:
            l_max, r_max = max(l_max, height[left]), max(r_max, height[right])

            if l_max <= r_max:
                res += l_max - height[left]
                left += 1
            else:
                res += r_max - height[right]
                right -= 1

        return res