백준_Java_14719_빗물

문제

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

이번 글에서는 백준 온라인 저지의 14719번 문제, "빗물" 문제를 다뤄보겠습니다.
2차원 세계에 블록이 쌓여있고, 비가 내린 후 고일 수 있는 물의 총량을 계산하는 문제입니다.

---

풀이

문제의 핵심 아이디어

어떤 칸에 고일 수 있는 물의 양은 다음과 같이 계산할 수 있습니다:

1. 해당 칸에서 왼쪽 방향으로 가장 높은 블록과 오른쪽 방향으로 가장 높은 블록 중 더 낮은 값을 찾습니다.
2. 그 값에서 현재 칸의 블록 높이를 뺀 값이 고일 수 있는 물의 양입니다.
   • 식으로 나타내면:

     물의 양 = Math.min(왼쪽 최대 높이, 오른쪽 최대 높이) - 현재 칸의 높이

3. 위 계산을 모든 칸에 대해 수행한 후, 이를 모두 더하면 전체 고인 물의 양을 구할 수 있습니다.

Pre-computation

효율적인 풀이를 위해 사전 계산을 활용합니다.
왼쪽 최대 높이와 오른쪽 최대 높이를 미리 계산하여, 각 칸에 대해 빠르게 물의 양을 계산합니다.

풀이 과정

예를 들어서 아래 예제가 주어졌을 때, 아래처럼 계산할수 있습니다.

인덱스	1	2	3	4	5	6	7	8
blocks	3	1	2	3	4	1	1	2

 

1. 왼쪽 최대 높이 배열 (leftMax) 계산:

• (leftMax[i]): (i) 칸의 왼쪽 방향에서 가장 높은 블록의 높이.
• leftMax[0] = blocks[0].
• leftMax[i] = Math.max(leftMax[i-1], blocks[i]) (1 ≤ (i) < (size)).

인덱스	1	2	3	4	5	6	7	8
blocks	3	1	2	3	4	1	1	2
leftMax	3	3	3	3	4	4	4	4

 

2. 오른쪽 최대 높이 배열 (rightMax) 계산:

• (rightMax[i]): (i) 칸의 오른쪽 방향에서 가장 높은 블록의 높이.
• rightMax[size-1] = blocks[size-1].
• rightMax[i] = Math.max(rightMax[i+1], blocks[i]) ((size-2) ≥ (i) ≥ 0).

인덱스	1	2	3	4	5	6	7	8
blocks	3	1	2	3	4	1	1	2
rightMax	4	4	4	4	4	2	2	2

 

3. 고인 물의 양 계산:

• (ans += Math.min(leftMax[i], rightMax[i]) - blocks[i]) (모든 칸에 대해).

인덱스	1	2	3	4	5	6	7	8
고인빗물높이	3	3	3	3	4	2	2	2
블록의높이	3	1	2	3	4	1	1	2
고인빗물의양	0	2	1	0	0	1	1	0

시간 복잡도

• (O(n)): 왼쪽 최대 높이와 오른쪽 최대 높이를 각각 한 번씩 순회하며 계산.
• 총 (O(n))으로 매우 효율적입니다.

코드

아래는 효율적인 풀이를 구현한 Java 코드입니다:

package Implementation.P14719;

import java.io.*;
import java.util.*;

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

        int H, W;
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        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 result = process(blocks);
        bw.write(result + "\n");

        bw.flush();
        br.close();
        bw.close();
    }

    static int process(int[] blocks) {
        int ans = 0;
        int size = blocks.length;
        int[] leftMax = new int[size];
        int[] rightMax = new int[size];

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

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

        // Calculate trapped water
        for (int i = 0; i < size; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - blocks[i];
        }

        return ans;
    }
}