[Leetcode] 42. Trapping Rain Water

🖥️ 시작하며

Python

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

        res = 0
        H = len(height)

        leftMax = [0] * H
        rightMax = [0] * H

				# 왼쪽 최대 높이 벽 저장
        leftMax[0] = height[0]
        for i in range(1, H):
            leftMax[i] = max(leftMax[i - 1], height[i])

				# 오른쪽 최대 높이 벽 저장
        rightMax[H - 1] = height[H - 1]
        for i in range(H - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

				# 계산
        for i in range(H):
            res += min(leftMax[i], rightMax[i]) - height[i]

        return res

C++

class Solution {
public:
    int trap(const std::vector<int>& height) {
        if (height.empty()) {
            return 0;
        }

        int H = height.size();
        int res = 0;

        std::vector<int> leftMax(H);
        std::vector<int> rightMax(H);

        // 왼쪽에서부터 최대 높이 저장
        leftMax[0] = height[0];
        for (int i = 1; i < H; ++i) {
            leftMax[i] = std::max(leftMax[i - 1], height[i]);
        }

        // 오른쪽에서부터 최대 높이 저장
        rightMax[H - 1] = height[H - 1];
        for (int i = H - 2; i >= 0; --i) {
            rightMax[i] = std::max(rightMax[i + 1], height[i]);
        }

        // 물을 잡을 수 있는 양 계산
        for (int i = 0; i < H; ++i) {
            res += std::min(leftMax[i], rightMax[i]) - height[i];
        }

        return res;
    }
};

소감

부록

참고문헌