[Algorithm/Java] 백준 14719번 - 빗물

---

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

---

🔍 문제 풀이

문제 도식화

배운 점

처음에는 2차원 배열을 선언하고,
각 열마다 블록의 높이만큼 1을 채우는 방식으로 시뮬레이션을 시도했다.

이후 위에서 아래로 내려가면서 빈 칸(0)을 기준으로 양옆이 벽(1)으로 막혀 있는지를 판단하여,
물이 고이는 위치를 찾으려 했다.

하지만 직접 구현해보니,

1. 블록 위아래 구조를 체크해야 하고
2. 각 줄마다 경계를 확인해야 하며
3. 범위 설정이 복잡해지는 문제점이 있었다.

결국, 구글 서치를 통해 이 문제는 2차원 배열이 아니라 1차원 배열로도 해결이 가능하다는 사실을 알게 되었다.

입력 배열이 각 열의 블록 높이를 나타내므로,
현재 위치를 기준으로 왼쪽과 오른쪽의 최대 높이만 알면 고일 수 있는 물의 양을 계산할 수 있었다.

앞으로는 더 단순한 방식이 있는지 먼저 고민해보는 습관을 들여야 겠다.

💻 전체 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        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[] arr = new int[w];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<w; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int ans = 0;
        // 맨 왼쪽과 오른쪽 벽 제외 (생략가능)
        for(int i=1; i < w-1; i++){
            // 왼쪽 최댓값
            int leftMax = -1;
            for(int j=0; j<i; j++){
                if(arr[j] > leftMax) leftMax = arr[j];
            }

            // 오른쪽 최댓값
            int rightMax = -1;
            for(int j=i+1; j<w; j++){
                if(arr[j] > rightMax) rightMax = arr[j];
            }

            int min = Math.min(leftMax, rightMax);
            int rain = min - arr[i];
            if(rain > 0) ans += rain;
        }

        System.out.println(ans);
    }
}