Menu

Subscribe

[JAVA/LeetCode] Top 100 Liked Question: 42. Trapping Rain Water

HEESOO on Leetcode

👀 문제

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

👊 도전

1. 설계

  1. i 위치에서 왼쪽, 오른쪽으로 max 높이를 구한다.
  2. 둘 중 작은 값-내 높이 가 i에서 물의 영역이다.

2. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
 *
 * @author HEESOO
 *
 */
class Solution {
    public int trap(int[] height) {
        if(height.length==0) return 0;
        int answer=0;
        int[] left=new int[height.length];
        int[] right=new int[height.length];
        
        // 왼쪽으로 max 높이 저장
        left[0]=height[0]; 
        for(int i=1;i<height.length;i++){
            left[i]=Math.max(height[i], left[i-1]);
        }
        // 오른쪽
        right[height.length-1]=height[height.length-1];
        for(int i=height.length-2;i>=0;i--){
            right[i]=Math.max(height[i], right[i+1]);
        }
        
        // 물 영역 계산
        for(int i=0;i<height.length;i++){
            answer+=Math.min(left[i], right[i])-height[i];
        }
        
        return answer;
    }
    
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. DP를 이용한다
    • i 위치에서 물 영역을 계산하려면 왼쪽 오른쪽에서 경계를 찾아야 한다. DP를 사용하지 않고 Brute Force로 진행하면 i위치에 따른 left, right max 높이를 계속 구해야 한다. 이 값은 변하는 것이 아니기 때문에 dp에 넣고 한 번만 체크하는 것이 더 시간을 단축시킨다.
    • left[i]는 i 기준 왼쪽에서 가장 큰 높이를 저장한다.
    • 이전까지의 최대 높이(left[i-1])와 현재 내 높이(height[i]) 중 큰 값을 left[i]에 저장한다.
    • right도 같다.
  2. 물을 계산한다
    • water[i]=min(left[i], right[i])-height[i]이다.
    • 왼쪽, 오른쪽 최대 높이에서 작은 높이까지만 물을 담을 수 있으므로 min을 통해 둘 중 하나를 선택한다.
    • 내 높이까지는 물을 채울 수 없으므로 height[i]를 뺀다.

👏 해결 완료!