<Hard> Trapping Rain Water (LeetCode : C#)

이도희·2023년 3월 11일

leetcode

알고리즘 문제 풀이

목록 보기

32/185

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

📕 문제 설명

구조물 형태를 나타내는 음의 정수가 아닌 정수 배열이 주어질 때 비 내린 후 물의 양 반환하기

Input
음의 정수가 아닌 정수 배열
Output
물의 양

예제

height에 따라 검은색 구조물이 그림과 같이 나타나진다. 구조물 사이를 보면 더 높이가 낮은 구조물 만큼 사이에 물이 쌓이게 될 때 전체 물의 양을 반환하면 된다.

풀이

시도 1.

실패 (시간 초과)

각 행을 모두 층으로 생각하고 쌓는 방식
1. 현재보는 높이가 이전 높이보다 큰 경우 -> 물 차는 케이스 (현재보는 높이만큼의 물 저장 후 해당 높이의 물 초기화)
(+ 이때 maxHeight보다 작은 경우 현재 높이에 대한 물을 추가로 저장)
2. 현재보는 높이가 이전 높이보다 작거나 같은 경우 현재 높이~maxHeight 층까지 물저장

public class Solution {
    public int Trap(int[] height) {

        int maxHeight = -1;
        int curHeight = -1;
        int water = 0;

        int[] storedWater = new int[height.Max()];

        for (int i = 0; i < height.Length; i++)
        {
            if (height[i] > curHeight)
            {
                for (int j = 0; j < height[i]; j++)
                {
                    water += storedWater[j];
                    storedWater[j] = 0;
                }

                if (height[i] < maxHeight)
                {
                    for (int j = height[i]; j < maxHeight; j++)
                    {
                        storedWater[j]++;
                    }
                }
            }
            else
            {
                for (int j = height[i]; j < maxHeight; j++)
                {
                    storedWater[j]++;
                }
            }

            curHeight = height[i];
            maxHeight = maxHeight > curHeight ? maxHeight : curHeight;
        }

        return water;
    }
}

예시처럼 큰 수 + 0이 번갈아 나오는 경우 시간적으로 매우 손해..! (배열 전체 돌면서 물 추가하고 전체 돌면서 저장을 계속 하기에)

풀이 1.

시간복잡도 : O(N)
결국 최대 막대에 초점을 두면 된다. 왼쪽에서와 오른쪽에서의 최대 막대를 미리 찾아두고 특정 인덱스에서 더 작은 쪽을 택한 후 자신의 길이를 빼면 물의 양이 구해진다.

public class Solution {
    public int Trap(int[] height) {
        int water = 0;
        int length = height.Length;
        int[] maxLeft = new int[length];
        int[] maxRight = new int [length];

        maxLeft[0] = height[0];
        maxRight[length-1] = height[length-1];
        
        for (int i = 1; i < length; i++)
        {
            maxLeft[i] = Math.Max(maxLeft[i-1] , height[i]);
        }

        for (int i = length - 2; i >= 0; i--)
        {
            maxRight[i] = Math.Max(maxRight[i+1], height[i]);
        }

        for (int i = 0; i < length; i++)
        {
            water += Math.Min(maxLeft[i], maxRight[i]) - height[i];
        }   
        
        return water;
    }
}