[알고리즘] 백준 14719 빗물

백준 14719

시도

중첩 for문을 이용해 현재 탐색하는 높이의 인덱스와 그 보다 더 낮은 높이를 가진 인덱스의 인덱스 차이 값을 결과에 더하려고 하였다. 그러나 이 부분은 많은 반례를 가지게 했다. 4 1 1 2 의 경우 2가 나와야하지만, 3이 나오는 등의 반례가 있었다.

풀이

한 높이에 대해서 좌, 우를 탐색해야했다. 현재 높이가 있는 인덱스를 기준으로 왼쪽과 오른쪽에 가장 높은 높이가 얼마인지 찾은 뒤, 왼쪽과 오른쪽 중에서 더 낮은 높이의 값을 찾아 현재 탐색하고 있는 인덱스의 높이 값을 빼주는 과정을 반복하면 된다.

가령 현재 높이가 1이고 왼쪽에서 가장 높은 값이 3 오른쪽에서 가장 높은 값이 4라면, 높이가 1인 위치 위에 담기는 물의 양은 3-1인 2칸 만큼이 담기게 되는 것이다.

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[] heights = new int[W];

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


        for (int i = 1; i < W-1; i++) {
        	// 현 위치 기준으로 왼쪽 오른쪽 가장 높은 높이 값 초기화
            int left = 0;
            int right = 0;
            
            // 왼쪽에서 가장 높은 높이를 찾는다.
            for (int j = 0; j < i; j++) {
                left = Math.max(heights[j], left);
            }

			// 오른쪽에서 가장 높은 높이를 찾는다.
            for (int j = i + 1; j < W; j++) {
                right = Math.max(heights[j], right);
            }

			// 왼쪽과 오른쪽 가장 높은 높이 중에서 더 낮은 높이 값을 찾아 현재 인덱스의 높이 값을 뺀 뒤, 결과 값에 더해준다.
            if (heights[i] < left && heights[i] < right) {
                result += Math.min(left, right) - heights[i];
            }
        }

        System.out.println(result);

    }
}