14719 빗물 (C#) [Gold V]

이미지를 누르면 문제로 이동합니다.

 

2차원 세계의 세로 길이 H와 가로 길이 W가 주어지고, 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 배열로 주어질 때,

빗물이 내리면 고이는 빗물의 총량을 출력하여라.

(바닥은 항상 막혀있고, 양 옆은 막혀있지 않습니다)

 

 

풀이 방법

Stack을 활용해서 풀이하는 방법을 공유하겠습니다.

 

내려가는 계단

왼쪽부터 오른쪽으로 높이를 Stack에 넣으면서 계산을 합니다.

1번, 2번, 3번을 넣고 4번을 넣을 때, Stack.Peek()의 값보다 현재 높이가 더 높습니다.

즉, 빗물을 채울 수 있는 조건을 의미합니다.

 

빗물이 채워지기 위해서는 빗물이 채워지는 공간 양 옆에 블록 기둥이 필수적으로 있어야합니다.

4번을 넣을 때에는 반대쪽 기둥의 높이를 알아야합니다.

 

stack.Push(list[i]);
maxH = Math.Max(maxH, list[i]);

반대쪽 기둥의 높이를 알기위해 반복문을 사용할 수는 없으니 매번 넣을때마다 가장 높은 기둥을 갱신해줍니다.

maxH에 현재까지의 가장 높은 기둥의 높이를 저장했습니다.

그럼 빗물이 쌓이는 높이는 현재 높이와 maxH중 더 작은 값이 됩니다.

 

int value = Math.Min(maxH, list[i]) - stack.Peek();

2, 3번을 채우는 상황에서는 위 value만큼 채울 수 있게됩니다.

 

현재까지의 상황은 내려가는 계단과 평지만 있을 때에만 해결이 가능합니다.

문제가 되는 상황은 올라가는 계단이 있을 때 입니다.

 

올라가는 계단

올라가든 계단이 있을 때에는 지금까지의 방법으로는 해결이 안됩니다.

3번을 넣을 때 2번 공간에 빗물이 2만큼 채워져야 하는 상황임에도 1만큼 채워집니다.

 

이런 상황에도 대처할 수 있도록 높이를 업데이트 해줘야합니다.

3번을 Stack에 넣을 때, 2번 공간에 1만큼 빗물이 채워져서 높이가 2가 되었다고 가정해보겠습니다.

그렇다면 4번을 넣을 때, 그 차이인 1만 더 넣어주면 목표 빗물 크기인 2가 완성이 됩니다.

 

Queue<int> temp = new Queue<int> ();

{ // 빗물 계산
    stack.Pop();
    temp.Enqueue(list[i]);
}

while (temp.Count > 0)
	stack.Push(temp.Dequeue());

3번을 넣을 때, 2번을 Stack에서 뺀 후에 높이를 새로 업데이트하여 다시 넣어주며 로직을 완성합니다.

 

 

정답 코드

public class Solution
{
    public int solution(int H, int W, List<int> list)
    {
        int answer = 0;
        int maxH = 0; 

        Stack<int> stack = new Stack<int> ();
        for (int i = 0; i < list.Count; i++)
        {
            int h = Math.Min(maxH, list[i]);

            Queue<int> temp = new Queue<int> ();
            while (stack.Count > 1 && stack.Peek() < list[i])
            {
                int value = stack.Peek();
                answer += Math.Max(0, h - value);
                stack.Pop();
                temp.Enqueue(list[i]); 
            }

            while (temp.Count > 0)
                stack.Push(temp.Dequeue()); 

            stack.Push(list[i]);
            maxH = Math.Max(maxH, list[i]);
        }
        return answer;
    }
}

 

 

class Program
{
    static void Main(string[] args)
    {
        Solution solution = new Solution();

        string[] inputs = Console.ReadLine().Split(' '); 
        int H = int.Parse(inputs[0]);
        int W = int.Parse(inputs[1]);

        List<int> list = new List<int>();
        Console.ReadLine().Split(' ').ToList().ForEach((str) => { list.Add(int.Parse(str));}); 


        int result = solution.solution(H, W, list);
        Console.WriteLine(result); 
    }
}