[백준] 14719번문제. 빗물 - Java

문제 : https://www.acmicpc.net/problem/14719

14719번: 빗물

 

각 칸에서 담을 수 있는 빗물의 양을 찾는 방법은 다음과 같다.

• 먼저, 각 칸마다 담을 수 있는 빗물의 최대 높이는 해당 칸의 왼쪽 벽과 오른쪽 벽 중 낮은 쪽의 높이이다.
  • 이 때, 양 옆의 벽이 꼭 해당 칸의 바로 옆에 붙어있을 필요는 없다.
  • 각각의 칸에서 왼쪽, 오른쪽을 바라본다고 생각했을 때, 눈에 보이는 가장 높은 벽의 높이를 찾으면 된다.
    • 예시 1번에서 벽의 높이로 [3, 0, 1, 4]가 주어졌는데, 각각의 칸에서 왼쪽을 바라봤을 때 보이는 가장 높은 벽의 높이는 [0, 3, 3, 3]이고, 오른쪽을 바라봤을 때 가장 높은 벽의 높이는 [4, 4, 4, 0]이다.
• 각 칸에 벽이 존재할 경우, 해당 벽의 높이 만큼은 빗물을 받을 수 없다.

이를 정리하면 다음과 같은 식으로 정리된다.

• i번째 칸이 담을 수 있는 빗물의 양 = min(왼쪽 벽의 높이, 오른쪽 벽의 높이) - 해당 칸의 벽의 높이

이 때, 벽이 한 쪽에만 존재하는 경우(양 끝 지점의 경우)에는 빗물을 받을 수 없으므로 계산할 필요가 없다.

 

소스코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        if (w < 3) {
            // 가로 방향으로 최소 3칸 이상의 공간이 준비되지 않으면 빗물을 받을 수 없음
            System.out.println(0);
            return;
        }

        int[] walls = new int[w];
        for (int i = 0 ; i < w; i++) {
            walls[i] = sc.nextInt();
        }

        int[] leftWalls = calcLeftWalls(walls);
        int[] rightWalls = calcRightWalls(walls);

        int answer = 0;
        for (int i = 1; i < walls.length - 1; i++) {
            // 양 끝 지점에서는 빗물을 모을 수 없음
            answer += Math.min(leftWalls[i], rightWalls[i]) - walls[i];
        }

        System.out.println(answer);
    }

    public static int[] calcLeftWalls(int[] walls) {
        int[] leftWalls = new int[walls.length];
        int height = walls[0];
        for (int i = 0; i < walls.length; i++) {
            if (walls[i] > height) {
                height = walls[i];
            }
            leftWalls[i] = height;
        }
        return leftWalls;
    }

    public static int[] calcRightWalls(int[] walls) {
        int[] rightWalls = new int[walls.length];
        int height = walls[walls.length - 1];
        for (int i = walls.length - 1; i >= 0; i--) {
            if (walls[i] > height) {
                height = walls[i];
            }
            rightWalls[i] = height;
        }
        return rightWalls;
    }
}