[Gold V] 빗물 - 14719 (Java)

문제 요약

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

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

---

문제 분석

왼쪽과 오른쪽에서 각각 반대편으로 이동하며, 현재 위치기준으로 시작점부터 현지점까지 가장 높은값을 저장하는 배열 생성 및 저장

그후 순차탐색하며 위 두배열의 현재위치의 값 중 min값을 전체 더해 결과 출력.

---

코드

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

public class Main {
    static int H, W;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        int[] Hmap = new int[W];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < W; i++){
            Hmap[i] = Integer.parseInt(st.nextToken());
        }
        int leftToRightMaxHeight = 0;
        int[] leftToRightMap = new int[W];
        int rightToLeftMaxHeight = 0;
        int[] rightToLeftMap = new int[W];
        for(int start = 0, end = W-1; start < W; start++, end--){
            // 왼쪽에서 오른쪽으로 이동하면서 왼쪽방향의 최대 높이를 저장
            leftToRightMaxHeight = Math.max(leftToRightMaxHeight, Hmap[start]);
            leftToRightMap[start] = leftToRightMaxHeight;
            // 오른쪽에서 왼쪽으로 이동하면서 오른쪽방향의 최대 높이를 저장
            rightToLeftMaxHeight = Math.max(rightToLeftMaxHeight, Hmap[end]);
            rightToLeftMap[end] = rightToLeftMaxHeight;
        }
        int result = 0;
        for(int i = 0; i < W; i++){
            int minHeight = Math.min(leftToRightMap[i], rightToLeftMap[i]);
            if(minHeight > Hmap[i]){
                result += minHeight - Hmap[i];
            }
        }
        System.out.println(result);
    }
}

---