[Leetcode] 42. Trapping Rain Water

 

[문제]

https://leetcode.com/problems/daily-temperatures/

 

 

 

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

 

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

 

---

 

문제 파악

• 들어오는 값을 보며 스택에 값을 집어넣고 조건부 pop()
• pop()하면서 기준점과의 차를 구함
• 해당 차의 누적합을 구하기

접근 방법

<aside> 💡 -배열을 돌며 기준점 선정. 배열은 앞 인덱스부터 순차적으로 돈다.

• 빗물을 가두는 벽(wall)의 기준 : 스택.peek() > left (왼쪽 벽)
• pop()하는 기준 : left(왼쪽 벽) ≥ 배열 요소 -그 외에 기준점보다 작으면 모두 push()
• 기준 조건에 걸리면 기준점과의 차 구하기 : left - pop() & 누적 sum
• 배열을 돌며 가장 높은 벽으로 인해 뒤의 요소 push() 후 pop() 되지 않음 ⇒ 스택이 빌 때까지 while문 돌며 pop()

-스택의 역순을 따라 새로 기준점 선정 *단순히 스택을 순회해야 하므로 기준점 선정 시 pop() 대신 peek()으로 지정 *right - pop() & 누적 sum

</aside>

코드 구현

 

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int sum=0;int left=0;
        for(int i=0;i<height.length;i++){
            while (!stack.isEmpty() && left<=height[i]){
                int pop = stack.pop();
                sum+=(left-pop);
            }
            stack.push(height[i]);
            if(height[i]>left) left=height[i];
        }
        int right=0;
        while (!stack.isEmpty()){
            if(right<stack.peek()) right=stack.peek();
            int pop = stack.pop();
            sum+=(right-pop);
        }
        return sum;
    }
}

 

실행 흐름 (pop() 시)

sum:0-0=누적합 0
sum:1-0=누적합 1
sum:1-1=0 누적합 1
sum:2-1=1 누적합 2
sum:2-0=2 누적합 4
sum:2-1=1 누적합 5
sum:2-2=0 누적합 5
//for문 end
//남은 스택 순회
sum:1-1=0 누적합 5
sum:2-2=0 누적합 5
sum:2-1=1 누적합 6
sum:2-2=0 누적합 6
sum:3-3=0 누적합 6

6

배우게 된 점

-아이디어를 떠올리고 구상하기까지가 시간이 걸렸던 문제인데, 막상 풀고보니 코드가 간결함

-스택 순회 시 기준점을 알맞게 선정하는 것이 중요한 것 같다.