[Baekjoon]

문제 링크

백준 14719 - 빗물

문제

문제가 간단하고 재미있었다.

4 4
3 0 1 4

위와같이 2차원세계의 높이, 넓이와 각 기둥의 높이값이 주어진다.
빗물이 고일 수 있는 최대치를 구하는 문제이다.

풀이

처음에는 뭔가 Stack 자료구조에 적합한 입력이라고 생각해서 고민을 해봤지만 쉽지 않았다. Stack은 peek값과 현재 확인하는 값 두가지를 비교해서 뭔가 결정해낼 수 있어야 한다. 하지만 이 문제에서는 더 넓은 범위를 확인해야하기 때문에 복잡해질 것 같았다.

투포인터를 활용해 문제를 해결했다.
빗물이 고이는 경우는 양쪽에 자신보다 큰 기둥이 있는 경우이다.

1. 현재 i번째까지 기둥의 최대값의 인덱스를 left에 저장한다.

2. block[left] 보다 크거나 같은 기둥이 나온 경우 그 사이에는 빗물이 고인다. 따라서 그 사이에 고이는 빗물의 양을 계산해서 answer을 업데이트 한다.

이 풀이의 문제점은 처음 left인덱스가 갱신이 되지 않을 때이다. 또 마지막 기둥이 큰 기둥이라는 보장이 없다. 이에 대한 처리를 추가로 해줘야 한다.

ex)

4 8
4 1 2 3 3 1 1 1

따라서 1, 2번 과정을 진행해 준 후 마지막에 추가로 남은 것들에 대한 계산을 진행한다.
더 크거나 같은 기둥이 나온 경우는 처리해줬으므로 1,2,번을 진행한 후 left와 right 사이의 block에서 크기가 증가하는 경우는 없다. 즉 left 방향에 가장 큰 기둥이 존재한다.

따라서 right에서 시작해서 peek값을 업데이트 하며 answer을 추가로 업데이트 해준다.

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

public class Main{

    private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {


        int H, W, answer = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        int[] block = new int[W];

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

		//1,2,번 과정
        int left = 0, right = 0;
        while(right<W){
            if(block[left] <= block[right]) {
                for (int i = left + 1; i < right; i++) {
                    answer += block[left] - block[i];
                }
                left = right;
            }
            right++;
        }
		
        //추가 작업
        int peek = block[right-1];
        for(int i= right-1; i>left; i--){
            peek = Math.max(peek, block[i]);
            answer+= peek-block[i];
        }

        System.out.println(answer);
        br.close();
    }
}

더 좋은 풀이

다른 사람 풀이를 확인하며 더 이해하기 쉽고 간단한 풀이를 보았다.

논리는 다음과 같다.

어떤 위치 i에서 고이는 빗물의 양은 i기준 좌측 최대값 기둥 leftMax[i]와 우측 최대값 rightMax[i] 중 작은 값과 block[i]를 빼준 값이다.

leftMax와 rightMax를 모두 초기화해둔 후 위의 작업을 진행하며 빗물의 양을 계산할 수 있다.

https://www.acmicpc.net/source/62389138