문제

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.

제한사항

• n == height.length
• 1 $\leq$ n $\leq$ 2 * $10^4$
• 0 $\leq$ height[i] $\leq$ $10^5$

접근1

담장의 높이가 주어졌을 경우 채울 수 있는 물의 용량을 구하는 문제였어요.

전개 방식
1. 최좌측부터 시작offset해서 담장 인덱스를 확장시키며 담을 수 있는 물의 용량을 더해요.
2. 확장된 담장이 offset보다 크면 offset을 기준으로 물의 용량을 구해요.
3. 그 외의 경우 확장 값을 업데이트하면서 적절한 용량을 구합니다.

풀이한지 오래되서 복기하면서도 헷갈리네요... 우선 해당 풀이는 마지막에 offset보다 작은 담장만 존재하면 구할 수 없는 풀이긴 합니다.

답안

class Solution {
    public int trap(int[] height) {
        if(height.length <= 1)
            return 0;

        int answer = 0;

        int offset = height[0];
        int left = 0, right = 1;
        while(left < height.length - 1){
            if(offset > height[right]){
                right++;
                if(right >= height.length){
                    ++left;
                    right = left + 1;
                    offset = height[left];
                }
            } else {
                answer += getValue(height, left, right);
                left = right;
                right++;
                offset = height[left];
            }
        }
        return answer;
    }


    private int getValue(int[] height, int left, int right){
        if(left >= height.length - 1 || right >= height.length)
            return 0;
        int ret = 0;
        int offset = height[left];
        for(int i = left + 1; i < right; ++i){
            ret += Math.max((offset - height[i]), 0);
        }
        return ret;
    }
}

접근2

결국 Leet Code에서 제공하는 답을 봤어요... 투 포인터를 활용해서 풀었어요.

1.left를 0, right를 height.size - 1로 잡고 각 담장의 높이를 max로 둬요.
2. left < right
2-1. left 위치가 max보다 크면 업데이트
2-2. 아니면 left - max 값을 answer에 더함
2-3. 그리고 left 증가
3. 그 외
3-1. right 위치가 max보다 크면 업데이트
3-2. 아니면 right - max 값을 answer에 더함
3-3. 그리고 right 감소
4. 2~3번을 반복하여 최종적으로 범위를 좁히면서 용량을 업데이트해요.

해당 방식은 각 left, right의 최대 높이를 기억해두면, 용량을 채워야 하는 부분을 업데이트할 때 적어도 해당 상황에선 이만큼의 물을 채울 수 있다는 보장이 존재한다는 전제가 있어 성립을 하게 되요. 쓰고도 무슨 이야긴지 모르겠네요. 풀이한지 오래되었어요... 다시 정리해볼게요 ㅠ

답안

class Solution {
    public int trap(int[] height) {
        if(height.length <= 1)
            return 0;

        int answer = 0;
        int left = 0, right = height.length - 1;
        int left_max = height[left], right_max = height[right];
        while(left < right){
            if(height[left] < height[right]){
                if(height[left] > left_max){
                    left_max = height[left];
                } else{
                    answer += (left_max - height[left]);
                }
                ++left;
            } else{
                if(height[right] > right_max){
                    right_max = height[right];
                } else{
                    answer += (right_max - height[right]);
                }
                --right;
            }
        }
        
        return answer;
    }
}