[리트코드] 42. Trapping Rain Water / Javascript

문제주소 :https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

---

<문제 설명>

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

 

Constraints:

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

 

<풀이법>

▒ 한줄 개념: dp ▒ 

얼마전에 본 코딩테스트에서 처음 풀어봤었는데, 다시 보니까 반가웠다.

 

DP를 이용하여 푸는 문제이다. 

가장 쉽게 생각하면, 비가 담기는 범위는 자신의 양쪽에 대해 가장 높은 벽들이 기준이 된다.

아래의 그림은, [0,1,0,2,1,0,1,3,2,1,2,1] 의 벽에 비가 내린 모습을 보인 것이다.

5번 칸을 기준으로 보면, 5번 칸에 담기는 빗물은 왼쪽에서 가장 높은 벽(3번 칸) 과 오른쪽에서 가장 높은 벽(7번 칸) 중 낮은 높이인 3번 칸에서 현재 칸의 높이를 뺀 만큼의 높이가 된다.

빗물이 담기려면 양쪽이 막혀야 하기 때문에, 양쪽에 있는 가장 높은 두 벽 중 더욱 낮은 벽이 빗물의 기준이 될 수 있는 높이라는 뜻이다. 이를 dp로 표현하면, 다음과 같다.

 

빗물의 양 = min(왼쪽에서 높은 높이, 오른쪽에서 높은 높이) - 현재 칸의 높이

 

여기서 dp를 사용하는 것이, 각 칸마다 일일히 양쪽의 최대 높이를 찾으려고 하면 n^2의 시간이 소요될 수 밖에 없다.

이를 줄이기 위해, 왼쪽에서 오른쪽으로 가며 가장 높은 높이를 기록하는 배열 하나와, 오른쪽에서 왼쪽으로 가며 가장 높은 높이를 기록하는 배열 하나를 각각 만든다.

height : [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
toRight :  [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
toLeft :    [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]

 

이렇게 할 경우, 위치 i에 대해 양쪽의 가장 높은 높이를 굳이 구하지 않아도, 왼쪽에서 가장 높은 벽은 toRight[i], 오른쪽에서 가장 높은 벽은 toLeft[i]가 된다. 

이전의 예시를 그대로 들어서 5번 칸에서 빗물이 쌓이는 값을 구한다고 하면, 높이: 0, 왼쪽 높은 높이 = 2, 오른쪽 높은 높이 = 3 이다. 이때 위의 3가지 배열을 확인해보면, height[5] = 0, toRight[5] = 2, toLeft[5] = 3이다. 따라서 이 값을 이용하면 쉽게 빗물의 양을 알 수 있는 것이다.

 

이 배열의 값들을 먼저 구한 dp 공식에 대입하면, 다음과 같이 표현되고, 이것이 이 문제의 핵심 코드가 된다.

dp[i] = min(toRight[i], toLeft[i]) - height[i]

 

<코드(Javascript)>

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let answer = 0;
    
    let toRight = new Array(height.length);
    let toLeft = new Array(height.length);
    
    toRight[0] = height[0];
    toLeft[height.length-1] = height[height.length-1];
    
    for(let i = 1; i < height.length; i++){
        toRight[i] = Math.max(height[i],  toRight[i-1]);
        toLeft[height.length-1-i] = Math.max(height[height.length-1-i], toLeft[height.length-i]);
    }
    
    for(let i = 0; i < height.length; i++)
        answer += Math.min(toLeft[i], toRight[i]) - height[i];
    
    return answer;
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest