[Baekjoon] 14719번 빗물 (Java) 문제 풀이 [Gold 5]

문제

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

14719번: 빗물

 

어떻게 풀 것인가?

우리가 흔히 말하는 빡구현 문제이다.
 

• 현재 블록의 높이보다 높은 블록이 왼쪽에 있어야 한다.
• 현재 블록의 높이보다 높은 블록이 오른쪽에 있어야 한다.
• 첫, 마지막 블록에는 빗물이 고일 수 없다.

인덱스 별로 모이는 빗물의 정보를 더해준 다음 출력해주면 된다. 현재 인덱스를 기준으로 왼쪽에서 가장 높은 블럭과 오른쪽에서 가장 높은 블럭을 구해준 다음, 현재 블럭이 두 블럭보다 낮은지 확인 후, 둘 중에 더 낮은 기둥을 기준으로 낮은 기둥에서 현재 기둥높이를 빼 주어 빗물이 고일 수 있는 높이를 계산해준다,

 

풀면서 놓쳤던점

생각보다 오래 걸렸다. 특정 알고리즘을 사용해야하는 것에 대해서 많은 고민을 했다.
 

이 문제를 통해 얻어갈 것

구현 문제 연습
 

내 코드 

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

class Main {
    static int H;
    static int W;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        int[] Harr = new int[W];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < W; i++) {
            Harr[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(Harr[j], left);
            }

            for (int j = i + 1; j < W; j++) {
                right = Math.max(Harr[j], right);
            }

            if (Harr[i] < left && Harr[i] < right) result += Math.min(left, right) - Harr[i];
        }
        System.out.println(result);

    }


}

 

참고

https://moonsbeen.tistory.com/247

[백준]14719: 빗물 - JAVA