3주차. 배열(빗물 트래핑)

08. 빗물 트래핑

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

Trapping Rain Water - LeetCode

 

 

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

- 예제1
  📝입력

height = [0,1,0,2,1,0,1,3,2,1,2,1]

  💻출력

6

  
 - 예제2

  📝입력
 

height = [4,2,0,3,2,5]

  💻출력
 

9

    
📌풀이
1. 투포인트 활용(1ms, 43.3mb)

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

    while(left < right){
        leftMax = Math.max(height[left], leftMax);
        rightMax = Math.max(height[right], rightMax);

        if(leftMax <= rightMax){
            answer += leftMax - height[left--];
        }else{
            answer += rightMax - height[right--];
        }

    }
    return answer;
}

 

- 왼쪽, 오른쪽 각각의 최대 높이의 벽을 구한 후, 왼쪽 오른쪽 포인트를 이동시키며 빗물이 받아질 깊이를 구함

- 대충 사진처럼 왼쪽 끝의 left, 오른 쪽 끝의 right 포인터가 이동하면서 이전 높이가 비교할 자신의 높이보다 크다면 그 높이를 빼서 빗물 높이를 구함

 

(2023.01.18 추가)

2. Stack 활용(13ms, 43.3 mb)

public int trapStack(int[] height) {
    Stack<Integer> stack = new Stack<>();
    int answer = 0;
    for(int i = 0; i < height.length; i++){
        // 비교하려는 높이가 스택에 들어있는 값보다 클 때
        // 스택에서 pop해야 되기 때문에 empty 확인
        while(!stack.isEmpty() && height[i] > height[stack.peek()]){
            int top = stack.pop();
            // 스택이 비었는지 여부를 또 확인해야함. 스택 안에 값이 없다면 pop한 높이만 남은 것이기 때문에 비교할 필요가 없음 받을 빗물이 없기 때문에
            if(stack.isEmpty()) break;

            // 현재 비교할 높이와 스택에 들어있는 높이 사이의 길이를 구해야함, 빗물이 어느정도의 길이만큼 있는지 알아야 되기 때무에
            int distance = i - stack.peek() - 1;
            // 물의 깊이를 구한다
            int watter = Math.min(height[i], height[stack.peek()]) - height[top];
            answer += distance * watter;
        }
        stack.push(i);
    }
    return answer;
}

노란색 1이라 되어 있는 부분 1이 아니라 2입니다.

- 투포인트 방식은 깊이를 구했다면, Stack을 활용할 경우 빗물이 받아진 길이와 깊이를 동시에 구한다.

- 높이를 좀 더 올리고 살펴보자. 스택에 맨 앞에 들어있는 높이와 비교해서 현재의 값이 높다면 stack에 들어있는 이전 높이와 비교를 하게 되는데, 이때 받아질 빗물의 길이와 높이를 구함.

 

- 그림은 비교대상이 height[7]일때의 과정을 그린거다. 4와 5 인덱스 사이의 빗물은 이미 구한 상태.

-  height[7]이 스택 상단에 위치한 height[6] 보다 크니 반복문을 돌 것이다.

-  6부터 pop하고 5가 없는 상태에서 4와 비교를 하겠죠? 그래서 같은 높이기 때문에 빗물이 없다고 판단 그대로 스택에서 빼버림

-  다음 인덱스 4를 pop해서 3과 비교를 하는데 이때의 서로의 길이는 3, 높이 차이는 2만큼 되더라

 

그림도 개판인데 설명도 개판인 것 같다. 아무튼 이런 두가지의 방식으로 빗물을 구하는데, 투포인트 방식이 시간면으로 더 효율적이다.