LeetCode 42. Trapping Rain Water 자바 문제 풀이

문제

Trapping Rain Water - LeetCode

문제 해결 방법

• 물을 받기위해서 최소한 1,0,1의 높이가 필요하므로, 최소한 3개이상의 엘레맨트가 필요합니다.
• 알고리즘

• 체크하길 원하는 포지션을 기준으로 왼쪽과 오른쪽에서 가장 높은 블럭 수를 구합니다.

• 두 높은 수에서 작은수 만큼 물을 채울수 있습니다.
• 이제 포지션의 블럭수를 확인해서 채울수 있는 물의 높이를 뺍니다.

• 모든 포지션을 반복합니다.
• 위 알고리즘을 사용하기 위해서 미리 루프문을 돌려서 오른쪽의 가장 높은 블럭수와 왼쪽의 가장 높은 블럭수를 미리 구해야 합니다.

• 아래와 같이 필요한 수를 확인할수 있습니다.

Github Link

https://github.com/eunhanlee/LeetCode_42_TrappingRainWater_Solution.git

시간복잡도: O(n), 공간복잡도: O(n)

public class Solution {
    /**
     * 바 사이에 쌓일 수 있는 물의 양을 계산합니다.
     *
     * @param height 바의 높이를 나타내는 배열
     * @return 바 사이에 쌓인 총 물의 양
     */
    public static int trap(int[] height) {
        int n = height.length;
        if (n <= 2) {
            return 0;
        }

        // 각 인덱스의 왼쪽에 있는 바들의 최대 높이를 저장하는 배열
        int[] leftMax = new int[n];
        // 각 인덱스의 오른쪽에 있는 바들의 최대 높이를 저장하는 배열
        int[] rightMax = new int[n];
        // 총 물의 양을 저장하는 변수
        int maxWater = 0;

        // 각 인덱스의 왼쪽에 있는 바들의 최대 높이를 계산합니다.
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // 각 인덱스의 오른쪽에 있는 바들의 최대 높이를 계산합니다.
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // 각 바에 대해 쌓인 물을 계산합니다.
        for (int i = 1; i < n - 1; i++) {
            // 현재 바의 왼쪽과 오른쪽 중 가장 높은 바의 높이를 찾습니다.
            int minBarHeight = Math.min(leftMax[i], rightMax[i]);
            // 최소 바 높이가 현재 바의 높이보다 크다면,
            // 현재 바 위에 물이 쌓일 수 있습니다.
            if (minBarHeight > height[i]) {
                // 쌓인 물의 양은 최소 바 높이에서 현재 바의 높이를 뺀 값입니다.
                maxWater += minBarHeight - height[i];
            }
        }

        // 총 쌓인 물의 양을 반환합니다.
        return maxWater;
    }
}