[LeetCode- Ch3. 배열] 5. 빗물 담기 # [+ 분할과 정복]

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

Trapping Rain Water - LeetCode

 

 

문제 해결 [Divide & Conquer]
1. 물이 차는 영역 결정 -> Math.min
-> 왼쪽벽과 오른쪽 벽의 값의 차이 만큼 물이 찬다.
2. 밑의 높이만큼 빼야한다. -> Math.min -밑의 높이

3. 필요한 자료구조

left[]  : 왼쪽 벽 최대 높이 배열

right[] : 오른쪽 벽 최대 높이 배열

height [] : 밑의 높이 배열

 

문제 해결 방식

1.  왼쪽 벽 배열과 오른쪽 벽 배열을 만들어 직접 계산

2. 배열을 따로 만들지않고 for문을 이용해 maxLeft와 maxRight을 이용해 물의 양 구하는 방법

---

1.  왼쪽 벽 배열과 오른쪽 벽 배열을 만들어 직접 계산

 

class Solution {
    public int trap(int[] height) {
        // 문제 해결 [Divide & Conquer]
        // 1. 물이 차는 영역 결정 -> Math.min
        // -> 왼쪽벽과 오른쪽 벽의 값의 차이 만큼 물이 찬다.
        // 2. 밑의 높이만큼 빼야한다. -> Math.min -밑의 높이
        
        int n=height.length;
        int answer=0;
        int[] left = new int[n];
        int[] right = new int[n];
        
        //왼쪽 벽 높이 배열 작성
        //: [0]번 높이를 최대로 기준설정
        int max= height[0];
        left[0]=height[0];
        
        for(int i=1;i<n;i++){
            if(max>height[i]) 
                left[i]=max;
            
            else{
                left[i]=height[i];
                max=height[i];
            }
        }
        //항상 현재 위치에서의 왼쪽 벽 최대값을 나타내는 배열.
        
        //오른쪽 높이 배열 작성
        max=height[n-1];
        right[n-1]=max;
        for(int i=n-2;i>=0;i--){
            if(height[i]<max){
                right[i]=max;
            }else{
                right[i]=height[i];
                max=height[i];
            }
            
        }
        //항상 오른쪽 벽 높이의 최댓값을 나타낸다.
        
        //빗물을 계산
        //Math.min()을 이용해 왼쪽벽과 오른쪽벽의 높이중 낮은 높이를 적용
        for(int i=0;i<n;i++){
            answer+=Math.min(left[i], right[i])-height[i];
        }
        return answer;
    }
}

 

2. 배열을 따로 만들지않고 for문을 이용해 maxLeft와 maxRight을 이용해 물의 양 구하는 방법

 

 

class Solution {
    public int trap(int[] height) {
        int leftMax=Integer.MIN_VALUE;
        int rightMax=Integer.MIN_VALUE;
        int result=0;
        int n=height.length;
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                leftMax=Math.max(height[j],leftMax); 
            }
            rightMax=Integer.MIN_VALUE;
            for(int k=n-1;k>=i;k--){
                rightMax=Math.max(height[k],rightMax);
            }
            
            result+=Math.min(leftMax, rightMax)-height[i];
        }
        
        return result;
    }
}

 

---

1.  왼쪽 벽 배열과 오른쪽 벽 배열을 만들어 직접 계산

class Solution {
    public int trap(int[] height) {
        int n=height.length;
        int answer=0;
        int[] left= new int[n];
        int[] right= new int[n];
        //왼쪽 벽 최댓값 배열
        //오른쪽 벽 최댓값 배열
        int leftMax=Integer.MIN_VALUE;
        int rightMax=Integer.MIN_VALUE;
        
        for(int i=0;i<n;i++){
            leftMax=Math.max(leftMax, height[i]);
            left[i]=leftMax;
        }
        for(int i=n-1;i>=0;i--){
            rightMax=Math.max(rightMax, height[i]);
            right[i]=rightMax;
        }
        
        //01 122223 333
        //12 223333 333
        for(int i=0;i<n;i++){
            answer+=(Math.min(left[i],right[i])-height[i]);
        }
        return answer;
    }
}

 

2. 배열을 따로 만들지 않고 for문을 이용해 maxLeft와 maxRight을 이용해 물의 양 구하는 방법

class Solution {
    public int trap(int[] height) {
        int n=height.length;
        int answer=0;
        //현재 위치에서 왼쪽 벽과 오른쪽 벽 최대찾기
        int leftMax=Integer.MIN_VALUE;
        
        for(int k=0;k<n;k++){
            for(int i=0;i<=k;i++){
                leftMax=Math.max(leftMax, height[i]);   
            }
            int rightMax=Integer.MIN_VALUE;
            for(int j=n-1;j>=k;j--){
                rightMax=Math.max(rightMax, height[j]);
            }
            //System.out.println(leftMax+" "+rightMax+" "+height[k]);
            answer+=Math.min(leftMax, rightMax)-height[k];
        }
        return answer;
    }
}