LeetCode 42. Trapping Rain Water 빗물 트래핑

빗물 트래핑

높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라

 

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

 

---

이 문제는 O(n) 풀이가 가능하다.

 

문제 풀이의 핵심은 아래와 같다.

• 투 포인터를 이용해 문제를 푼다.
• left, right 포인터를 이동하며 얼만큼의 물이 쌓일지를 계산한다.
• 계산을 할때 기준점은 왼쪽, 오른쪽 각각 가장 높은 높이이다.

 

풀이설명

 위 그림에서 회색 빗금(이하 volume)은 차오른 물을 뜻한다.

인덱스 2와 6사이에 채워진 volume은 left max의 값인 2가 한계다.

left max와 right max 두 벽이 있을 때, 더 낮은 벽의 높이만큼 물이 차기 때문이다.

 

0번 인덱스를 left, 6번 인덱스를 right라 할 때,

각 지점에서 조건에 따라 한칸씩 움직이며 volume을 계산한다.

 

 - two pointer가 교차할때까지 반복문을 실행한다.

- leftMax, rightMax의 값을 계산한다.

  - Math.max(someMaxValue, num);

- leftMax 가 rightMax 보다 작을 때 volume을 계산하기 위해 조정할 포인터는 left다.

- Max의 값에서 현재 조회중인 값을 뺀 만큼 volume에 더한다.

  - volume += someMaxValue - height[leftOrRight];

- rightMax의 값이 더 작은 경우는 right 포인터를 이동한다.

 

구현 코드

class Solution {
    public int trap(int[] height) {
        int volume = 0;
        int left = 0;
        int right = height.length - 1;
        // 문제 풀이의 핵심이 될 요소다
        int leftMax = height[left];
        int rightMax = height[right];

        while (left <= right) {
            // 포인터가 움직일때 마다 max 값을 갱신한다.
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            // 아래 조건을 이용하여 two pointer 를 움직이고 연산처리한다.
            if (leftMax <= rightMax) {
                // 볼륨량 계산
                volume += leftMax - height[left];
                // left 포인터 이동
                left++;
            } else {
                volume += rightMax - height[right];
                right--;
            }
        }

        return volume;
    }
}