[Leetcode] 42. Trapping Rain Water - JS

https://leetcode.com/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150

1. 문제 분석

문제분석
--------------------
- 양의 정수 n으로 이루어진 배열이 주어진다.
- n은 바의 높이를 의미한다.
- 비가 오고 난 후 얼마나 많은 양의 물을 가둘 수 있는지 계산하라.

제한조건
--------------------
- n == height.length
- 1 <= n <= 2 * 10^4
- 0 <= height[i] <= 10^5

 

 

2. 접근 방법

접근방법
--------------------
물을 가두기 위해서는 높이를 가진 왼쪽 바와 오른쪽 바가 존재해야한다.

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

파란색 부분에 물을 채우기 위해선 어떻게 해야할까?

우선 index 2인 곳의 양옆에는 높이가 1인 바가 있어서 물이 1이 있다는 것을 알 수 있다.
하지만 index 1의 높이가 1이면 어떨까?
이때는 왼쪽에 높이가 2인 인접한 바가 있고 
오른쪽에는 높이가 3인 바가 있어서 물이 유지될 수 있다.

물과 바 사이의 어느정도 거리가 있을 때 물을 가둘 수 있는지는 어떻게 판단할 수 있을까?

방법은 왼쪽과 오른쪽의 최대 높이값을 유지하는 것이다.

Two Pointer를 사용하여 문제를 해결해보자.

[2,1,0,1,3,2]
 L         R

L = 0 // 현재 왼쪽 바
R = height.length - 1 // 현재 오른쪽 바
leftMax = 2 // 왼쪽 바 최대 높이값
rightMax = 2 // 오른쪽 바 최대 높이값
water = 0 // 물의 양

왼쪽 포인터(L) < 오른쪽 포인터(R)을 만족하면 반복한다.

1. leftMax, rightMax 중 작은 값을 가진 포인터를 이동시킨다.

더 작은 값의 포인터를 이동시키는 이유는 물이 바 사이에 갇힐 때, 
물을 가질 수 있는 높이가 둘 중 더 작은 바의 높이만큼 가질 수 있기 때문이다.

leftMax = 2, rightMax = 2로 동일하기에 둘중 하나의 포인터(R)를 이동시켰다.

[2,1,0,1,3,2]
 L       R

2. R 포인터가 이동했으니 rightMax 값과 비교하여 더 큰 값으로 갱신해준다.

rightMax = 3

3. 물을 계산한다.

water += rightMax - R = 3 - 3 = 0

오른쪽 바를 움직였으니 오른쪽 바의 최대값과 현재 오른쪽 바와의 차이를 구하면 된다.
이 때 왼쪽 바는 이미 높이가 오른쪽 바 보다 크거나 같으니 상관하지 않아도 된다.

이렇게 한번의 반복이 끝나고
L < R 조건을 만족하지 않을 때 까지 반복한다.

결과적으로 L < R 조건을 만족하지 않아서 반복이 종료되면 그 때의 물을 반환한다.

 

 

3. 코드

var trap = function(height) {
    let left = 0;
    let right = height.length - 1;
    let leftMax = height[left];
    let rightMax = height[right];
    let water = 0;

    while (left < right) {
        if (leftMax < rightMax) {
            left++;
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
        } else {
            right--;
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
        }
    }
    return water;
};

물 높이를 구하기 위해 왼쪽, 오른쪽으로 나눠서

한쪽의 최대 높이값과 현재 막대의 높이값의 차를 가지고

물의 양을 구하고 이를 누적하여 답을 도출해내었다.

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

30분동안 방법을 고민해도 갈피를 아예 잡지 못하였다. 물을 어떻게 하면 가둘 수 있을까?를 똑같이 고민했고, 바로 인접한 경우의 물은 쉽게 구할 수 있다고 생각했다. 하지만 막대 사이의 거리가 존재할 때의 물을 어떻게 구할 수 있을지 생각하지 못했다.

 

Two pointer를 이용해 왼쪽, 오른쪽 구간을 나누고 물 높이를 구할 때, 왼쪽 또는 오른쪽의 최신의 최대 높이값을 추적하여 현재 바의 높이값과 비교하여 물의 양을 구할 수 있다는 방법도 있다는 것을 알게되었다.

 

Two pointer에 대해 좀 더 문제를 풀어보면서 익혀야겠다.