백준 14719 빗물 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/14719

풀이는 다음과 같다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st1.nextToken());
        int W = Integer.parseInt(st1.nextToken()); //W 1이면 답 0

        StringTokenizer st2 = new StringTokenizer(br.readLine());

        Stack<Integer> s = new Stack<>();

        int start = Integer.parseInt(st2.nextToken());
        int answer = 0;

        while(st2.hasMoreTokens()) { //도중에 더 높은거 만나면, 싹다 비워내고 고인 물 세주는 로직 (1, 4번)
            int tmp = Integer.parseInt(st2.nextToken());
            if(tmp >= start) {
                while(!s.isEmpty()) {
                    answer += start - s.pop();
                }
                start = tmp;
            }
            else {
                s.add(tmp);
            }
        }



        if(!s.isEmpty() && s.size() > 1) { //전부 끝나고 나서, 도중에 더 높은걸 안만났다고 생각해보자 (2번, 3번, 5번)
            int end = s.pop();

            while(true) {
                if(s.isEmpty()) break;
                int cur = s.pop();
                if(cur > end) {
                    end = cur;
                }
                else {
                    answer += end - cur;
                }

            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }


}

풀이 안의 주석에서, 1번부터 5번까지는 위의 그림을 의미하는것이다.

풀이

스택을 이용해서 풀었다.
뭔가 예전부터
내가 원하는 값을 만나면, 원하는 값 이외의 값을 만날때까지
기존의 값들을 와다다다 제외하면서 원하는 로직대로 처리해주는 내용.

이러한 내용은 보통 스택으로 풀었기에,
어.. 이친구도 스택인가..? 를 생각해서 풀어줬다.

지금부터 문제풀때 생각했던 내용을 설명하겠다.

기록된 높이의 벽보다
그 이상의 벽을 예로 들겠다. (위 그림의 1번 4번)
주어진 숫자들(벽의 높이들 전체)을 전부 입력받으며 계산했다.
예를 들어,
4 1 1 3 5 를 생각해보자.
기록된 높이의 벽 = 4
그다음 벽 1 < 4 (스택에 넣기)
그다음 벽 1 < 4 (스택에 넣기)
그다음 벽 3 < 4 (스택에 넣기)
그다음 벽 5 >= 4
기록된 높이보다 더 높은게 나왔으므로, 기존에 스택에 있던 친구들을 전부 꺼내서 빗물 고여주고, (4-1, 4-1, 4-3 더해주고)
기록된 높이를 갱신해준다.(start = tmp)

while(st2.hasMoreTokens()) { //도중에 더 높은거 만나면, 싹다 비워내고 고인 물 세주는 로직 (1, 4번)
            int tmp = Integer.parseInt(st2.nextToken());
            if(tmp >= start) {
                while(!s.isEmpty()) {
                    answer += start - s.pop();
                }
                start = tmp;
            }
            else {
                s.add(tmp);
            }
        }

그다음, 모든 숫자를 사용했는데,
기록된 높이 이상의 벽이 안나와서 스택이 텅 비지 않은채로 바로 위의 while문을 마쳤다면..?
(위의 2번, 3번, 5번 경우)
해당 경우가 아래의 로직이다.
바로 위에서 설명한 굵은 글씨의 로직을 이해했다면, 이 로직도 쉽게 이해가 갈 것이다.

if(!s.isEmpty() && s.size() > 1) { //전부 끝나고 나서, 도중에 더 높은걸 안만났다고 생각해보자 (2번, 3번, 5번)
            int end = s.pop();

            while(true) {
                if(s.isEmpty()) break;
                int cur = s.pop();
                if(cur > end) {
                    end = cur;
                }
                else {
                    answer += end - cur;
                }

            }
        }

풀이 하나 더!
구현으로 풀었다. 주석에 설명이 있어 이해할 수 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(st1.nextToken());
        int w = Integer.parseInt(st1.nextToken());

        int[] blocks = new int[w];

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



        int answer = 0;

        //빗물이 고일 수 있는 블럭 하나하나마다, 양 옆을 탐색하여 해당 블럭 하나에 고이는 빗물을 더해줄 예정임.
        //3 0 1 4 에서 0은, 양옆의 3과 4에 가로막혀 빗물이 고이고, 3-0만큼의 빗물이 고인다. 이런식으로 
        for(int i = 1 ; i < w-1 ; i++) { //처음과 끝은 빗물이 고일 수 없으므로 제외
            int curH = blocks[i];

            int lm = 0; //어느 index 기준으로 왼쪽에서 높이최대 기록
            int rm = 0;

            for(int j = i-1 ; j >= 0 ; j--) {
                lm = Math.max(lm, blocks[j]);
            }

            for(int j = i+1 ; j < w ; j++) {
                rm = Math.max(rm, blocks[j]);
            }

            //lm과 rm이 둘다 지금 현재 높이보다 높다면 빗물 고이므로,
            //둘 중 더 적은값(적은값을 기준으로 빗물이 고이니까)과 현재 높이를 빼줌
            if(lm > curH && rm > curH) answer += Math.min(rm, lm) - curH;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();

    }

}