[자바 알고리즘 인터뷰] 7장 배열 (2) 빗물 트래핑

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

 

 

- 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지를 계산하라

 

 

풀이 1) 투 포인터를 최대로 이동 

 

 

- 최대 높이의 막대까지 각각 좌우 막대 최대 높이 leftMax, rightMax가 현재 높이와의 차이만큼 물 높이 volume을 더해나간다. 

 

- 이 경우 적어도 낮은 쪽은 그만큼 항상 채워질것이기 때문에, 좌우 어느쪽이든 낮은 쪽은 높은 쪽을 향해서 포인터가 가운데로 점점 이동한다. 

- 오른쪽이 높다면 left+=1로 왼쪽 포인터가 이동하고, 왼쪽이 높다면  right-=1로 오른쪽 포인터가 이동한다. 

- 이렇게 하면 가장 높이가 높은 막대, 즉 '최대' 지점에서 좌우 포인터가 서로 만나게 되며 O(n)로 풀이가 가능하다. 

 

class Solution {
    public int trap(int[] height) {
        int volume = 0;
        int left = 0;
        int right = height.length -1;
        int leftMax = height[left];
        int rightMax = height[right];

        //투 포인터가 서로 겹칠 때까지 반복
        while(left<right) {
            leftMax = Math.max(height[left], leftMax);
            rightMax = Math.max(height[right], rightMax);

            //더 높은쪽으로 향해 투 포인터 이동
            if(leftMax <=rightMax) {
                //왼쪽 막대 최대 높이와의 차이를 더하고 왼쪽 포인터 이동
                volume += leftMax - height[left];
                left+=1;
            }else {
                //오른쪽 막대 최대 높이와의 차이를 더하고 오른쪽 포인터 이동
                volume += rightMax - height[right];
                right -=1;
            }
        }

        return volume;
    }
}

 

실행시간 : 0밀리초 

 

 

풀이 2) 스택 쌓기 

 

- 스택에 쌓아나가면서 현재 높이가 이전 높이보다 높을 떄, 즉 꺾이는 부분 변곡점(Inflections Point)을 기준으로 격차만큼 물이 쌓이는 양 volume을 채운다. 

 

- 이전 높이는 고정된 형태가 아니라 들쑥날쑥하기 때문에, 계속 스택으로 채워나가다가 변곡점을 만날 때마다 스택에서 하나씩 꺼내면서 이전과의 차이만큼 물에 쌓이는 양을 채워나간다. 

 

import java.util.*;

class Solution {
    public int trap(int[] height) {
       Deque<Integer> stack = new ArrayDeque<>();
       int volume = 0;

       for(int i=0; i<height.length; i++) {
        //변곡점을 만나는 경우 
        while(!stack.isEmpty() && height[i]>height[stack.peek()]) {
            //스택에서 꺼낸다. 
            Integer top = stack.pop();

            if(stack.isEmpty())
                break;

            //스택의 마지막 위치까지를 거리로 계산
            int distance = i-stack.peek() -1;

            //현재 높이 또는 스택의 마지막 위치 높이 중 낮은 값에 방금 꺼낸 높이의 차이를 물 높이로 지정 
            int waters = Math.min(height[i], height[stack.peek()]) - height[top];

            //물이 쌓이는 양은 거리와 물 높이의 곱
            volume += distance*waters;
        }

        //진행하면서 현재 위치를 스택에 삽입
        stack.push(i);
       }

       return volume;
    }
}

 

실행시간 : 8 밀리초