[LeetCode] 42. Trapping Rain Water (빗물 트래핑)

🔗 문제

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

Trapping Rain Water - LeetCode

 

📝 풀이

'투 포인터'를 사용하여 왼쪽, 오른쪽에서 가운데 방향으로 가면서 각 최대높이에서 해당 높이 값을 계산하면 된다.

 

💻 코드 (java)

class Solution {
    public int trap(int[] height) {
        int answer = 0;

        int left_max = 0;
        int right_max = 0;
        int left = 0;
        int right = height.length-1;


        while (left < right) {
            left_max = Math.max(height[left], left_max);
            right_max = Math.max(height[right], right_max);

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

        //System.out.println("answer = " + answer);
        return answer;
    }
}

 

💻 코드 (python)

from typing import List

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

        volume = 0
        left = 0
        right = len(height) - 1

        left_max = height[left]
        right_max = height[right]

        # print(left, right)
        # print(left_max, right_max)

        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 += 1
            else:
                volume += right_max - height[right]
                right -= 1

        return volume



height = [0,1,0,2,1,0,1,3,2,1,2,1]

ss = solution()
#ss.trap(height)

print(ss.trap(height))