[Baekjoon 14719] 빗물- JAVA

[Gold V] 빗물 - 14719

문제 링크

성능 요약

메모리: 14236 KB, 시간: 108 ms

분류

구현, 시뮬레이션

제출 일자

2025년 2월 10일 16:30:10

문제 설명

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

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

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

문제 풀이

각 위치에 고일 수 있는 빗물의 양을 구한 후 모두 합산하는 방식으로 풀이할 수 있다.

각 위치에서의 물 높이 결정:
어떤 위치 i에서 고일 수 있는 빗물의 높이는 좌우에 있는 가장 높은 벽에 의해 결정된다.

왼쪽에서 볼 때의 최대 높이를 $leftMax[𝑖]$오른쪽에서 볼 때의 최대 높이를 $rightMax[i]$ 그러면 해당 위치에서 실제로 채울 수 있는 빗물의 높이는 $water[i] = min(leftMax[i],rightMax[i])−block[i]$
단, 음수가 나오면 0으로 처리한다. (문제에서는 블록 높이가 항상 해당 값 이하이므로 음수가 나오지 않는다.)

전체 빗물의 양:
모든 위치에서의 빗물의 양을 더해주면 전체 고인 빗물의 양이 된다.

계산 방법:

배열을 한 번 순회하면서 각 위치까지의 왼쪽 최대 높이 leftMax를 계산한다.
배열을 역순으로 순회하면서 각 위치부터 오른쪽 끝까지의 오른쪽 최대 높이 rightMax를 계산한다.
마지막으로 각 위치에서 채울 수 있는 빗물의 양을 계산하고 합산한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] blocks = new int[W];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            blocks[i] = Integer.parseInt(st.nextToken());
        }

        int[] leftMax = new int[W];
        leftMax[0] = blocks[0];
        for (int i = 1; i < W; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], blocks[i]);
        }

        int[] rightMax = new int[W];
        rightMax[W - 1] = blocks[W - 1];
        for (int i = W - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], blocks[i]);
        }

        int totalWater = 0;
        for (int i = 0; i < W; i++) {
            totalWater += Math.min(leftMax[i], rightMax[i]) - blocks[i];
        }

        System.out.println(totalWater);
    }
}

코드 풀이

        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] blocks = new int[W];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            blocks[i] = Integer.parseInt(st.nextToken());
        }

• W는 가로 길이를 H에는 세로 길이를 저장한다.
• W개의 정수(각 위치의 블록 높이)가 주어지므로 이를 blocks 배열에 저장한다.

        int[] leftMax = new int[W];
        leftMax[0] = blocks[0];
        for (int i = 1; i < W; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], blocks[i]);
        }

• $leftMax[0]$는 첫 번째 블록의 높이로 초기화한다.
• $i = 1$부터 $W − 1$까지 순회하면서, 이전까지의 최대 높이와 현재 위치의 블록 높이 중 큰 값을 저장합니다.
• 이 배열은 각 위치까지 왼쪽에서 볼 때의 최대 벽 높이를 나타냅니다.

        int[] rightMax = new int[W];
        rightMax[W - 1] = blocks[W - 1];
        for (int i = W - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], blocks[i]);
        }

• $rightMax[W-1]$는 마지막 블록의 높이로 초기화한다.
• $i = W − 2$부터 0까지 역순으로 순회하면서, 오른쪽에서 볼 때의 최대 높이를 계산합니다.
• 이 배열은 각 위치부터 오른쪽 끝까지 볼 때의 최대 벽 높이를 나타냅니다.

        int totalWater = 0;
        for (int i = 0; i < W; i++) {
            totalWater += Math.min(leftMax[i], rightMax[i]) - blocks[i];
        }

• 모든 위치 i에 대해, 좌우에서 볼 때의 최대 벽 높이 중 작은 값과 현재 블록 높이의 차이가 그 위치에 저장될 수 있는 빗물의 양이다.
• 차이를 모두 합산하여 totalWater 변수에 저장한다.