Trapping Rain Water

📌 문제

• 위와 같이 빗물이 쌓인다.
• 빗물이 쌓인 높이를 구하라.

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

📌 문제 풀이

• 빗물이 쌓인다 -> 빗물이 언제 쌓이는 지에 대한 조건이 무엇인지 구해야 한다.

• 빗물은 조건을 따져보다 보면 ( 예시를 하나하나 따져보다보면 ) 왼쪽 큰놈과 오른쪽 큰놈 중 작은놈을 기준으로 만들어 지는 것을 알 수 있다. 그 중, 현재 자신의 높이를 빼주면 해당 빗물이 생기는 크기를 알 수 있다.
• 그러면, for loop를 돌면서 왼쪽에서 큰놈, 오른쪽에서 큰놈을 각각 구해주고, 현재값을 빼준 값이 0보다 크다면 result에 값을 더해주면 답이 나온다.
• 이 때, 위의 풀이를 그대로 풀면 O(n^2) 이 나온다. 이는 배열의 loop를 돌 때마다 왼쪽에서 큰놈, 오른쪽에서 큰놈을 매번 각각 구해야 되기 때문이다.
• 그래서 memoziation 맥락의 방법을 이용하면, O(n)으로 시간을 줄일 수 있다.

🔥 O(n)으로 풀기

• loop를 돌면서, 왼쪽에서 가장 큰 값을 해당 left 배열에 넣어준다.
• left 배열의 의미 = 나 ( i ) 이전 왼쪽에서 가장 컸던 값
• right 배열도 맥락은 같다. 다만 오른쪽에서 시작하니, 오른쪽에서 가장 컸던 값을 해당 배열에 넣어준다.



세팅된 left, right 배열값

📌 O(n^2) 풀이

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int trap = solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
        System.out.println(trap);
    }
    static class Solution {
        public int trap(int[] arr) {
            int count = 0;
            for(int i=1;i<arr.length-1;i++){
                int leftMax = 0;
                int rightMax = 0;
                for(int j=0;j<i;j++){
                    if(arr[j] > leftMax) leftMax = arr[j];
                }
                for(int j=arr.length-1;j>i;j--){
                    if(arr[j] > rightMax) rightMax = arr[j];
                }
                if(leftMax == 0 || rightMax == 0) continue;
                int current = Math.min(leftMax,rightMax) - arr[i];
                if(current>0) count+=current;
            }
            return count;
        }
    }
}

📌 O(n) 풀이

public class MainV2 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int trap = solution.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
//        System.out.println(trap);
    }
    static class Solution {
        public int trap(int[] arr) {
            int count = 0;
            int N = arr.length;

            int[] left = new int[N];
            int[] right = new int[N];

            int leftMax = arr[0];

            for(int i=1;i<N;i++){
                left[i] = leftMax;
                if(arr[i] > leftMax) leftMax = arr[i];
            }

            int rightMax = arr[N-1];

            for(int i=N-2;i>=0;i--){
                right[i] = rightMax;
                if(arr[i] > rightMax) rightMax = arr[i];
            }

            System.out.println(Arrays.toString(left));
            System.out.println(Arrays.toString(right));

            for(int i=0;i<N;i++){
                int num = Math.min(left[i],right[i]) -arr[i];
                if(num>0) count += num;
            }
            return count;
        }
    }
}

📌 O(n^2) - O(n) 풀이 시간차이