LeetCode 42. Trapping Rain Water (Java) (Hard) (DP)

문제출처: https://leetcode.com/problems/trapping-rain-water/

Trapping Rain Water - LeetCode

 

문제이해

 

목표

하나의 배열이 주어진다. 배열에는 해당 인덱스 자리에 블럭의 높이의 값을 나태나는 정보가 주어진다. 
블럭과 블럭 사이에 빈공간이 있다면 물을 채울 수 있다. 정확한건 그림을 참조하자. 
 compute how much water it can trap after raining. 비가 오고 물이 얼마나 채워질지 구해보자.

 

 

풀이

 

첫번째 고안한 풀이

dp를 이용했다. dp[]에 기억을 하는 값은 다음과 같다.

예시) dp[j] = i => 높이 j가 가장 마지막으로 있었던 인덱스 번호 i  

 

주어진 배열 height만큼 탐색을 하는데 

 -> 그리고 해당 height배열의 인덱스 값(높이h) 만큼을 탐색해서

      => 방문했던 높이가 있다면 그 사이의 길이를 찾아서 물의 개수를 찾는다.

 

물의 개수를 다 찾을 수 있다. 

 

=> 정답은 도출되지만, 시간 복잡도로 봤을 때 실패에 가까운 코드이다. 

     최대 20000 * 100000 의 시간이 경과될 수 있음

 

 

다른 사람 코드를 본 코드

 

각 노드 기준으로 왼쪽 블럭들 중 가장 높은 블럭, 오른쪽 블럭들 중 가장 높은 블럭을 구한다.

그리고 구한 왼쪽, 오른쪽 블럭중 낮은 블럭에 자신의 블럭을 뺐을 때 => 자신의 블럭에 얼마나 물이 찰 수 있는지 알림 

answer += Math.min(right[i], left[i]) - height[i];

 

소스코드

첫번째 코드

import java.util.Arrays;

// https://leetcode.com/problems/trapping-rain-water/
public class TrappingRainWater {
    public int trap(int[] height) {
        int answer = 0;
        int[] dp = new int[100001];
        Arrays.fill(dp, -1);
        for (int i = 0; i < height.length; i++) {
            int h = height[i];
            if(h == 0){
                continue;
            }
            for (int j = 1; j <= h; j++) {
                if(dp[j] != -1){ // 방문했던 적이 있다면
                    answer += i - dp[j] - 1;
                }
                dp[j] = i;
            }
        }
        return answer;
    }
}

 

두번째 코드

import java.util.Arrays;

// https://leetcode.com/problems/trapping-rain-water/
public class TrappingRainWater {
    public int trap(int[] height) {
        int answer = 0;
        int N = height.length;
        int[] left = new int[N];
        int[] right = new int[N];
        int max = 0;
        for (int i = 0; i < N; i++) { // left
            if (max < height[i]) {
                max = height[i];
            }
            left[i] = max;
        }
        max = 0;
        for (int i = N-1; i >= 0; i--) { // right
            if (max < height[i]) {
                max = height[i];
            }
            right[i] = max;
        }
        // 정답 도출
        for (int i = 0; i < height.length; i++) {
            answer += Math.min(right[i], left[i]) - height[i];
        }
        return answer;
    }
}