[리트코드] 42. Trapping Rain Water <Java>

문제

---

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

Trapping Rain Water - LeetCode

 

 

풀이

---

내 풀이 :

왼쪽에서 부터 오른쪽으로 가장 최근에 높았던 높이에서 더 높은 높이를 만나면 그 사이의 값들의 높이차를 더해주었다.

위의 행동을 반대방향으로 한번 더 했다.

이 때, 주의할점은 같은 것을 두번 더하지 않기 위해 HashSet을 이용하여 문제를 풀었다.

 

<내풀이 코드>

class Solution {
    public int trap(int[] height) {
        
        int n = height.length;
        
        int answer = 0;
        int now_height = 0;
        int sum = 0;
        int lastIdx = 0;
        HashSet<String> set = new HashSet<>();
        
        for(int i = 0 ; i < n ; i++){
            if(now_height == 0 && height[i] == 0) { continue; }
            
            if(now_height == 0) { 
                now_height = height[i]; 
                lastIdx = i;
            }
            else if(now_height <= height[i]){
                answer += sum;
                
                sum = 0;
                now_height = height[i];
                
                set.add(lastIdx + "-" + i);
                lastIdx = i;
            }
            else{ 
                sum += (now_height - height[i]);            
            }
        }
        
        now_height = 0;
        sum = 0;
        for(int i = n - 1 ; i >= 0 ; i--){
            if(now_height == 0 && height[i] == 0) { continue; }
            
            if(now_height == 0) { 
                now_height = height[i]; 
                lastIdx = i;
            }
            else if(now_height <= height[i]){                
                if(set.add(i + "-" + lastIdx)){
                    answer += sum;

                    sum = 0;
                    now_height = height[i];
                    lastIdx = i;
                }else{
                    lastIdx = i;
                }
            }
            else{ 
                sum += (now_height - height[i]);            
            }
        }
        
        
        return answer;
    }
}

 

하지만 이렇게 할 경우 HashSet을 사용하여 중복 검사를 하기 때문에 속도가 느려지게 된다.

이렇게 중복 검사를 하지 않고 푸는 방식이 있어서 가져왔다.

 

알고리즘 순서

1. 왼쪽에서 오른쪽으로 현재 인덱스 까지 가장 높은 높이를 저장한다.
2. 1과 같은 방식으로 오른쪽에서 왼쪽 방향도 해준다.
3. 1의 결과와 2의 결과 중 더 작은 최대 높이 - 현재 인덱스의 높이 의 결과값을 answer 에 더해준다.

<전체코드>

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