[Baekjoon Online Judge] 14719. 빗물 (Java)

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

 

핵심

특정 지점을 기준으로 두 값을 찾는다.

1. 해당 지점의 블록 높이

2. 해당 지점을 기준으로 왼쪽의 땅에서 가장 높은 블록과 오른쪽 땅에서 가장 높은 블록 중에서 더 낮은 블록을 찾는다.

 

2번 값이 해당 지점에서 빗물이 최대로 쌓일 수 있는 높이이다.

따라서 2번과 1번의 차가 해당 지점에서 쌓일 수 있는 빗물의 최대 높이

(만약 이 차가 0 이하라면 빗물이 한 칸도 쌓일 수 없는 상태)

+ 양 끝은 빗물이 쌓일 수 없다.

구현

나는 왼쪽을 기준으로 현재 인덱스까지 지점에서 가장 높은 블록의 높이를 배열에 저장했다. (누적합)

e.g. highestFromLeft[10] : 0 ~ 10 지점 중에서 가장 높은 블록의 높이

 

오른쪽도 똑같이 구한 후 이를 활용

Code (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] height = new int[W + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            height[i] = Integer.parseInt(st.nextToken());
        }

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

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

        int total = 0;
        for (int i = 0; i < W; i++) {
            if (i == 0 || i == W - 1) {
                continue;
            }

            int side = Math.min(highestFromLeft[i - 1], highestFromRight[i + 1]);
            int diff = Math.max(0, side - height[i]);
            total += diff;
        }

        System.out.println(total);
    }
}