Trapping Rain Water

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

Trapping Rain Water - LeetCode

 

주어진 높이 배열에 물을 담을 수 있는 양을 체크하는 문제이다. 처음 문제를 보았을 때는 쉽게 풀 수 있을거라 생각했지만 막상 풀이를 시도하니 고려해야 할 문제들이 많았다. 좌우 높이 뿐만 아니라 바닥의 높이도 가변적이다 보니 넓이를 구하기가 쉽지 않았다.

 

바닥의 높이가 좌표마다 다른 점을 해결하기 위해 좌우 벽과 함께 계산된 바닥도 이동 시켜주는 방식으로 생각해주었다. 좌,우 포인트를 더 높은 곳으로 이동시키며 이미 계산한 벽의 높이 만큼은 바닥을 잘라준다고 생각하여 물의 양을 계산해주는 것을 반복하여 풀었다. 아래는 최종 코드이다.

public class Solution {  
    public int trap(int[] height) {  
  
        int answer = 0;  
        int bottom = 0;  
        int l = 0;  
        int r = height.length - 1;  
  
        while(l < r){  
            int leftHeight = height[l];  
            int rightHeight = height[r];  
            int minHeight = Math.min(leftHeight, rightHeight);  
            for(int i = l; i <= r; i++){  
                int nowHeight = height[i];  
                if(nowHeight < minHeight){  
                    answer += minHeight - Math.max(nowHeight, bottom);  
                }  
            }  
  
            bottom = minHeight;  
            if(leftHeight > rightHeight){  
                while(l < r && height[r] <= rightHeight){  
                    r--;  
                }  
            }else{  
                while(l < r && height[l] <= leftHeight){  
                    l++;  
                }  
            }  
        }  
  
        return answer;  
    }  
}

 

직접 풀이한 내용 외에도 다른 풀이에서 눈에 보였던 점은 좌우 벽의 최대 높이를 배열로 저장해두고 사용하는 방식이었다. 점을 이동시켜 현재 높이를 구하면서도 현재 높이에서 좌우 높이의 최대 값을 확인하는 방식으로 속도 효율이 좋았다. 해당 코드는 아래와 같다.

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int lmax[] = new int[height.length];   
        int rmax[] = new int[height.length];
        int l_max = height[0];
        for(int i=0;i<n;i++){
            l_max = Math.max(l_max,height[i]);
            lmax[i] = l_max;
        }
        int r_max = height[n-1];
        for(int i=n-1;i>=0;i--){
            r_max = Math.max(r_max,height[i]);
            rmax[i] = r_max;
        }
        int count = 0;
        for(int i=0;i<n;i++){
            count+=(Math.min(lmax[i],rmax[i])-height[i]);
        }
        return count;
    }
}