[백준 Baekjoon] 14719번 빗물 - JAVA

[백준 Baekjoon] 14719번 빗물 - JAVA

문제 풀이

특별한 알고리즘의 사용은 없는 구현을 사용한 문제이다. 빗물이 고이는 두가지 경우를 생각하여 각각 구해줌으로 문제를 풀었다.

1 왼쪽 기둥보다 오른쪽의 기둥이 큰 경우. 좌에서 우로 순회한다.
1.1 왼쪽 기둥의 높이를 h, 위치를 left에 저장하였다.
1.2 왼쪽 기둥보다 오른쪽 기둥이 큰거나 같은 경우 양 기둥 사이를 순회하며 두 기둥중 작은 기둥의 높이에서 뺄셈을 한다.
1.3 왼쪽 기둥과 위치를 새로 최신화 해준다.

2 왼쪽 기둥보다 오른쪽의 기둥이 작은 경우. 우에서 좌로 1에서 구한 마지막 왼쪽 기둥까지 순회한다.
2.1 1에서 구한 마지막 왼쪽 기둥까지의 빗물을 계산이 완료되어 마지막 왼쪽 기둥까지만 한다.
2.2 오른쪽 기둥의 높이를 h, 위치를 right에 저장하였다.
2.3 왼쪽 기둥과 오른쪽 기둥을 바꿔 1.2와 1.3를 수행한다.

문제 예시의 2번을 보면 이해가 빠르다.

0번 기둥부터 4번 기둥까지 1를 수행하여 구하고, 7번 부터 4번 기둥까지 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[] arr = new int[W];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int answer = 0;

        int h = arr[0], left = 0, right = W;
        for (int i = 1; i < W; i++) {
            if (h <= arr[i]) {
                h = Math.min(h, arr[i]);

                while (left++ < i - 1) {
                    answer += h - arr[left];
                }

                h = arr[i];
            }
        }

        h = arr[W - 1];
        for (int i = W - 1; i >= left; i--) {
            if (h <= arr[i]) {
                h = Math.min(h, arr[i]);

                while (right-- > i + 1) {
                    answer += h - arr[right];
                }

                h = arr[i];
            }
        }

        System.out.println(answer);
    }
}