BOJ) 빗물

빗물

14719번: 빗물

풀이

 

문제를 처음 맞이했을 때 생각한 것 보다는 꽤나 신경을 써야하는 문제였다.

 

먼저, 배열을 사용하지 않고 입력받은 값에 대해 구간의 max값을 구해줘서 답을 내주려고 했었다.

0으로 시작하는 구간이나 마지막 값이 0이면 빗물이 생성되지 않는다는 조건 때문에 포기했다.

 

그래서 배열을 만들고 위의 로직을 시도해볼까 했는데, 너무 복잡해지는 것 같아서 포기했다.

 

마지막으로 떠올린 것은, 한 구간에 대해 양 옆에 제일 높은 기둥 두개를 찾는 것이었다.

두 기둥 중에 낮은 크기의 기둥과 차이만큼 물이 고이기 때문에, 적절하다고 생각했다.

 

시작하는 지점과 마지막 지점은 빗물이 고이지 않기 때문에, 1~x크기-1 만큼 for문을 돌며 값을 구해주었다.

해당 인덱스에 대해 좌측과 우측에서 MAX 값을 찾고, 둘 중 MIN 값을 구했다.

이 값이, 현재 기둥보다 클 경우에만 물이 고이기 때문에, if문을 통해 해당 조건을 걸어주었다.

 

시작과 끝 두 개를 제외한 모든 지점을 탐색해서 답을 구했다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class RainWater_14719 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String size = br.readLine();
        int x = Integer.parseInt(size.split(" ")[1]);
        int[] blockArr = new int[x];

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

        for(int i=0; i<x; i++) {
            blockArr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(solution(blockArr, x));
        br.close();
    }

    private static int solution(int[] blockArr, int x) {
        int answer =0;

        for(int i=1; i<x-1; i++) {
            int leftMax = getLeftMax(blockArr, i);
            int rightMax = getRightMax(blockArr, i);

            int height = Math.min(leftMax, rightMax);
            
            if(height > blockArr[i]) {
            	answer += height - blockArr[i];
            }
        }
        return answer;
    }

    private static int getLeftMax(int[] blockArr, int i) {
        int result =0;
        for(int idx = i-1; idx>=0; idx--) {
            result = Math.max(result, blockArr[idx]);
        }
        return result;
    }

    private static int getRightMax(int[] blockArr, int i) {
        int result =0;
        for(int idx = i+1; idx<blockArr.length; idx++) {
            result = Math.max(result, blockArr[idx]);
        }
        return result;
    }
}