LeetCode - Trapping Rain Water

문제설명

배열이 주어진다. 배열은 각각의 벽의 높이를 뜻할때, 담을 수 있는 비의 총량을 구하여라.

난이도 Hard의 문제

풀이방법

풀이 방법은 아무래도 슬라이딩 윈도우와 비슷한 방식을 떠올렸다.
배열 전체를 돌아가면서 왼쪽벽,오른쪽 벽 높이의 min값과 현재 높이의 값을 빼준 값을
ans에 더해주면 답이 나오니까

코드

import java.lang.*;

class Solution {
    public int trap(int[] height) {
        int answer=0;
        
        for(int i=1; i<height.length-1; i++){
            int left= i-1;
            int right = i+1;
            int leftMax = height[i];
            int rightMax = height[i];
            
            while(left>=0){
                leftMax = Math.max(height[left],leftMax);
                left--;
            }
            
            while(right<height.length){
                rightMax = Math.max(height[right],rightMax);
                right++;
            }
            int min = Math.min(leftMax,rightMax);
            answer+=min-height[i];
            
        }
        return answer;
        
    }
}

결과

사실 Hard문제라길래 어 어렵겠다 생각하고 긴장하고 풀었는데, 생각보다 쉽게 풀렸다

는 개뿔,, 시간복잡도가 처참한 결과를 나타냈다 니 알고리즘 똥냄새 하는것 같았다.. for문내에 while문이 있다보니 아무래도 $O(n^2)$이 시간 복잡도로 나올 수 밖에 없었기 때문인 것으로 보인다.

해결책 2

두 가지 방법을 떠올렸다.
1. 스택으로 해결하는 방법
2. 2 Pointer를 이용하여 해결하는 방법

사실 스택으로 해결해보고자 했지만, 잘 떠올라지지 않았다.

그래서 2Pointer로 문제를 해결하려 했다

코드

import java.lang.*;

class Solution {
    public int trap(int[] height) {
    
        int ans = 0;
        int left=0;
        int right=height.length-1;
        
        if(height.length == 0) return 0;
        int leftMax = height[left];
        int rightMax = height[right];
        
        while(left<right){
            if(leftMax<=rightMax){
                ans += leftMax - height[left];
                left++;
                leftMax = Math.max(height[left],leftMax);
            }else{
                ans += rightMax -  height[right];
                right--;
                rightMax = Math.max(height[right],rightMax);
            }
        }
        
        return ans;
    
    }
}

결과 2

시간복잡도가 $O(n^2)$에서 $O(n)$으로 변경됐기 때문에, 좋은 결과가 나왔다.

풀이는 오래 걸리지 않았지만, 2 Pointer를 생각해내기란 쉽지 않았을 것 같다.

또한 언제나 빈문자열이 들어올 수 있으므로, 그에따른 처리를 생각해놓자.