[알고리즘 문제풀이] 백준 14719 빗물

이번주에 면접,, 다음주에도 면접,, 그치만 다음주에 코테 두 개,,🤯 알고리즘 문제풀이도 꾸준히 해야하는데,, 일정 관리가 쉽지가 않다 ! ! ! ! ! 으아,,

어쨌든 오랜만에 알고리즘 문제를 풀어보았다 ! 백준 14719 - 빗물을 풀었다. 근데 요거 요거 문제가 되게 익숙한 느낌 ? 사실 여기 저기서 많이 볼 수 있는 유명한 ? 웰논 ? 문제이기도 하고,

예전에 SWEA에서 비슷한 문제 소재 ? 물을 채우는 소재의 문제를 푼 적이 있고, 또 얼마 전에 본 기업 코테에서 ( 어딘지 언급해도 되나몰라서 안 함 ) 문제 소재는 물을 채우는게 아니었지만 풀이 방법은 아주아주 유사한 문제를 풀었다 !

근데 그 때는 풀긴 했는데 이번에 푼 거 보다 비효율적으로 풀었던 거 같아서 아쉬움이 남지만,, ( 오쨌든 다 풀어서 냈고 오쨌든 통과 했으니께 ? ) 안 그래도 복기를 하려고 했는데 이 문제를 풀게 되면서 다음주 면접에 더 좋은 풀이법을 알고갈 수 있어서 이 문제 풀기를 넘 잘한 거 같다 ! 💡

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.
비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제

입력 1

4 4
3 0 1 4

출력 1

5

입력 2

4 8
3 1 2 3 4 1 1 2

출력 2

5

입력 3

3 5
0 0 0 2 0

출력 3

0

풀이 방법

각 칸마다 어느 높이까지 물이 찰 수 있는지를 찾아내야하는 문제이다. 특정 열에 어떤 높이까지 물이 차는지의 기준이 되는 값은 그 열의 좌측에서 가장 높은 값, 우측에서 가장 높은 값인데 이제 그 두 값 중에서는 더 작은 값까지 물이 찰 수 있다.

즉 위에 첨부한 그림의 에를 보면 높이 2인 2열의 경우 좌측에서 가장 높은 값은 높이 3인 0열이고, 우측에서 가장 높은 값은 높이 4인 4열이다. 3과 4중에서는 3이 더 작기때문에 2열에는 높이 3까지 물을 채울 수 있는 것이다. 2열의 높이는 2였기 때문에 실제로 물이 차는 영역은 1칸인 것이다 !

이것을 코드로 구현하기 위해서 먼저 각 높이를 배열에 저장해주었다. 그리고 좌측 가장 높은 값을 저장하는 변수, 우측 가장 높은 값을 저장하는 변수 두 개를 두고, 각 열을 쭉 돌면서 각 열을 기준으로 좌측에서 가장 높은 값과 우측에서 가장 높은 값을 두 개의 배열에 각각 저장해주었다. 이후 좌, 우 두 값을 비교하여 더 작은 값을 기준으로 각 열에 찰 수 있는 물의 영역을 더해주었다.

각 열의 좌측 가장 높은 값, 우측 가장 높은 값을 찾아내는 것이 결국 관건인데, 이것을 O(N)으로 풀었다. 전체 풀이의 시간 복잡도 역시 O(N)이다 !

코드

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 st = new StringTokenizer(br.readLine());
        int h = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());

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

        int last = w-1;
        int left = heights[0];
        int right = heights[w-1];
        int[] lefts = new int[w];
        int[] rights = new int[w];
        for(int i=1; i<last; i++){
            if(left <= heights[i]) left = heights[i];
            if(right <= heights[last-i]) right = heights[last-i];
            lefts[i] = left;
            rights[last-i] = right;
        }

        int min;
        int sum = 0;
        for(int i=1; i<last; i++){
            min = Math.min(lefts[i], rights[i]);
            sum += (min - heights[i]);
        }
        bw.write(sum + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}