문제 링크

풀이

배열에 블록들의 높이를 저장한다.
양쪽 끝을 제외한 모든 요소들을 탐색하며 탐색하는 블록 기준으로 왼쪽과 오른쪽 블록들 중에 제일 높은 블록의 높이를 각각 구한다.

구한 두 값을 비교하여 더 작은 값을 구하고, 그 값이 현재 탐색 중인 블록보다 크면 그 만큼 빗물이 쌓일 수 있으므로 두 값을 빼서 result에 더해준다.

코드1

package BOJ;

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

public class sol14719 {
    static int h, w;
    static int[] blocks;
    static int result = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

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

        for (int i = 1; i <= w - 1; i++) {
            int leftMax = Integer.MIN_VALUE;
            int rightMax = Integer.MIN_VALUE;

            int curr = blocks[i];
            for (int j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, blocks[j]);
            }
            for (int j = i + 1; j <= w - 1; j++) {
                rightMax = Math.max(rightMax, blocks[j]);
            }
            if( Math.min(leftMax, rightMax) < curr) continue;
            result += Math.min(leftMax, rightMax) - curr;
        }
        System.out.println(result);
    }
}

코드2

코드1은 각 블록의 왼쪽/오른쪽 최대 높이를 매번 계산한다. 이 부분을 개선하여 미리 구해놓으면 시간복잡도를 $O(w^2)$ -> $O(w)$로 개선할 수 있다.

int[] leftMax = new int[w];
int[] rightMax = new int[w];

// 왼쪽 최대 누적
leftMax[0] = blocks[0];
for (int i = 1; i < w; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], blocks[i]);
}

// 오른쪽 최대 누적
rightMax[w - 1] = blocks[w - 1];
for (int i = w - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], blocks[i]);
}

// 이제 각 칸에서 계산
for (int i = 1; i < w - 1; i++) {
    result += Math.max(0, Math.min(leftMax[i - 1], rightMax[i + 1]) - blocks[i]);
}