백준 14719번: 빗물[JAVA]

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

14719번: 빗물

 

 

[정답 코드]

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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;

        for (int i = 1; i < W - 1; i++) { // 처음벽과 마지막벽에는 물이 고일수 없다
            int current = arr[i]; // 현재 벽의 높이
            int leftMax = current; // 왼쪽 벽
            int rightMax = current; // 오른쪽 벽
            for (int j = i - 1; j >= 0; j--) { // 왼쪽 벽 최대 높이 탐색
                if (arr[j] > current) {
                    leftMax = Math.max(leftMax, arr[j]);
                }
            }
            for (int j = i + 1; j < W; j++) { // 오른쪽 벽 최대 높이 탐색
                if (arr[j] > current) {
                    rightMax = Math.max(rightMax, arr[j]);
                }
            }
            if (Math.min(leftMax, rightMax) > current) { // 현재 벽보다 높은 벽이 양쪽에 있는 경우
                answer += (Math.min(leftMax, rightMax) - arr[i]);
            }
        }
        System.out.println(answer);
    }
}

 

[설명]

처음에는 구현문제가 쉬운 문제인줄 알았는데 풀면 풀 수록 구현 문제도 어렵다는걸 깨달았다. 이 문제는 다른 블로그들을 대부분 참고했다.

문제 풀이방법은 for문을 돌며 현재 벽 기준으로 왼쪽 벽 중 가장 높은벽과 가장 높은 오른쪽 벽을 구한 후, 그 벽들이 현재 벽보다 높을 경우 빗물이 고이기 때문에 높은 벽에서 현재 벽을 빼주면 그 차이 만큼 빗물이 쌓인다.

이때 문제의 핵심은 두가지가 있다.

1. 가장 왼쪽벽과 가장 오른쪽 벽에는 빗물이 고일 수 없다.

그래서 for문을 돌릴때 i = 1부터 시작되고 끝은 W - 1까지 한다. 

2. 현재 벽보다 높은 양쪽 벽중에 더 낮은 벽 기준으로 빗물이 고인다.

예를 들면 빨간 체크한 벽이 for문에서 현재 current 라고 했을 때, 왼쪽벽 중 가장 높은벽은 4 이고 오른쪽벽 중  가장 높은 벽은 2이다. 이때 그림으로 보면 알 수 있듯이 왼쪽벽을 기준으로 계산하는게 아닌 오른쪽 벽을 기준으로 계산해야 한다.