[BOJ] 빗물

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

풀이

빗물이 고이는 정도를 구해야한다.
고이는 정도를 측정하려면 왼쪽과 오른쪽의 벽 높이를 구해서 더 작은 값을 찾아야한다.
더 작은값이 빗물이 고이는 최고의 높이가 되기 때문이다.

벽의 높이의 최대 최소를 구하는 것은 시간상 비효율적이다.
그렇게 되면 매 탐색마다 좌, 우로 전체 조사를 결국 해야하기 때문에 다른 방법을 찾으려고 노력하였다.
인덱스를 서로 바꿔서 찾는 등 노력을 해보았지만
최종적으로 전체적으로 탐색을 한번 더 해보는 것이 맞았다.

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int answer = 0;
        int H = Integer.parseInt(str[0]);
        int W = Integer.parseInt(str[1]);
        int[] heights = new int[W];
        str = br.readLine().split(" ");
        for(int i = 0; i < W; i++) {
            heights[i] = Integer.parseInt(str[i]);
        }
        int sum = 0;

        for(int i = 1; i < heights.length; i++) {
            int leftMax = 0;
            for(int j = 0; j <= i ; j++) {
                leftMax = Math.max(leftMax, heights[j]);
            }

            int rightMax = 0;
            for(int j = i; j < W ; j++) {
                rightMax = Math.max(rightMax, heights[j]);
            }

            sum += Math.min(leftMax, rightMax) - heights[i];

        }
        System.out.println(sum);
    }

}

https://github.com/Win-9/Algorism/tree/main/BOJ/%EB%B9%97%EB%AC%BC