[Baekjoon(JAVA) - Alogorithm] 14719번: 빗물

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

 

---

Answer

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

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

            int[] blockArray = new int[W];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < W; i++) {
                blockArray[i] = Integer.parseInt(st.nextToken());
            }
            System.out.println(getRainBlockCnt(blockArray));
        } catch (IOException e) {
            System.err.println("ERROR : " + e.getMessage());
        }
    }

    static int getRainBlockCnt(int[] blockArray) {
        int rainBlockCnt = 0;

        for (int i = 1; i < blockArray.length - 1; i++) {
            int currentBlock = blockArray[i];
            int leftBlock = 0;
            int rightBlock = 0;
            int standardBlock = 0;

            for (int j = i - 1; j >= 0; j--) {
                if (blockArray[j] > currentBlock) {
                    leftBlock = Math.max(leftBlock, blockArray[j]);
                }
            }
            for (int j = i + 1; j < blockArray.length; j++) {
                if (blockArray[j] > currentBlock) {
                    rightBlock = Math.max(rightBlock, blockArray[j]);
                }
            }

            standardBlock = Math.min(leftBlock, rightBlock);
            if (standardBlock > currentBlock) {
                rainBlockCnt += standardBlock - currentBlock;
            }
        }
        return rainBlockCnt;
    }
}

 

Code Review

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    ...
} catch (IOException e) {
    System.err.println("ERROR : " + e.getMessage());
}

try-with-resources 구문으로 try에 객체의 자원을 받아서 `br.close()` 같은 코드 없이 try문이 끝나면 자동으로 자원을 반환한다.

`System.in`으로 사용자로부터 입력받은 데이터를 바이트 스트림으로 받는다.

`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 변환한다.

`BufferedReader` 클래스로 문자 스트림을 읽는다.

 

StringTokenizer st;
st = new StringTokenizer(br.readLine());
int H = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());

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

`StringTokenizer` 클래스로 입력받은 문자열을 default인 공백 구분자로 개별적인 토큰으로 분리한다.

이를 `st.nextToken()`으로 토큰 하나씩 가져온다.

 

블록이 쌓인 높이를 맨 왼쪽부터 차례대로 `blockArray` 배열에 추가한 후 `getRainBlockCnt(blockArray)` 메서드에서 빗물이 고인 총량을 구한다.

 

static int getRainBlockCnt(int[] blockArray) {
    int rainBlockCnt = 0;

    for (int i = 1; i < blockArray.length - 1; i++) {
        int currentBlock = blockArray[i];
        int leftBlock = 0;
        int rightBlock = 0;
        int standardBlock = 0;

        for (int j = i - 1; j >= 0; j--) {
            if (blockArray[j] > currentBlock) {
                leftBlock = Math.max(leftBlock, blockArray[j]);
            }
        }
        for (int j = i + 1; j < blockArray.length; j++) {
            if (blockArray[j] > currentBlock) {
                rightBlock = Math.max(rightBlock, blockArray[j]);
            }
        }

        standardBlock = Math.min(leftBlock, rightBlock);
        if (standardBlock > currentBlock) {
            rainBlockCnt += standardBlock - currentBlock;
        }
    }
    return rainBlockCnt;
}

문제에서 가장 중요한 부분이다.

1. 첫 블럭과 마지막 블럭은 빗물이 고일 수 없다.
2. 현재 블럭의 높이보다 높은 블럭이 좌우에 있어야 한다.
3. 좌우 블럭의 높이는 현재 블럭의 높이보다 커야 한다.
4. 좌우 블럭은 각각 현재 블럭 왼쪽에서의 최댓값과 오른쪽에서의 최댓값이어야 한다.
5. 좌우 블럭중 낮은 높이와 현재 블럭의 높이를 뺀 값이 현재 블럭에서의 빗물 높이이다.

 

위 조건을 생각해서 문제를 풀어보자.

for (int i = 1; i < blockArray.length - 1; i++) {
    int currentBlock = blockArray[i];
    int leftBlock = 0;
    int rightBlock = 0;
    int standardBlock = 0;

    ...
}

1번을 고려해서 첫 블럭과 마지막 블럭을 뺀 첫 반복문을 작성한다.

즉, i를 0이 아닌 1부터 `blockArray.length - 1`까지이다.

가로 블럭 하나마다 2번~5번을 구해야 하므로 for문에 현재 블럭, 왼쪽 블럭, 오른쪽 블럭, 기준 블럭 변수를 생성한다. (기준 블럭은 좌우 블럭중 낮은 높이를 구하는 변수이다.)

// 빗물 높이를 구할 수 있는 블럭만 구하기 (1)
for (int i = 1; i < blockArray.length - 1; i++) {
    int currentBlock = blockArray[i];
    int leftBlock = 0;
    int rightBlock = 0;
    int standardBlock = 0;

    // 현재 블럭의 왼쪽 블럭 구하기 (2, 3, 4)
    for (int j = i - 1; j >= 0; j--) {
        if (blockArray[j] > currentBlock) {
            leftBlock = Math.max(leftBlock, blockArray[j]);
        }
    }
    // 현재 블럭의 오른쪽 블럭 구하기 (2, 3, 4)
    for (int j = i + 1; j < blockArray.length; j++) {
        if (blockArray[j] > currentBlock) {
            rightBlock = Math.max(rightBlock, blockArray[j]);
        }
    }

    // 현재 블럭에서의 빗물 높이 구하기 (5)
    standardBlock = Math.min(leftBlock, rightBlock);
    if (standardBlock > currentBlock) {
        rainBlockCnt += standardBlock - currentBlock;
    }
}

괄호에는 위에서 말한 조건의 번호를 써놨다.

 

현재 블럭의 왼쪽 블럭을 구하기 위해 index는 `i - 1`부터 0까지를 구한다. 이때 현재 블럭의 높이보다 커야 빗물의 쌓일 수 있으며, 반복하면서 최대 높이를 구한다.

 

현재 블럭의 오른쪽 블럭을 구하기 위해 index는 `i + 1`부터 마지막까지를 구한다. 이때 현재 블럭의 높이보다 커야 빗물의 쌓일 수 있으며, 반복하면서 최대 높이를 구한다.

 

좌우 블럭의 최대 높이를 구했으면 이 중 낮은 높이인 블럭(기준 블럭)을 구한다. 이때 낮은 높이인 블럭이 현재 블럭의 높이보다 크면 빗물이 쌓인다. 조건에 맞다면 기준 블럭에 현재 블럭 높이를 뺀 값을 `rainBlockCnt` 빗물이 고인 블럭 갯수에 더한다.

 

이 로직을 반복하여 빗물이 고인 블럭 총개수를 구하여 return 한다.

 

Result

구현 문제라고 해서 만만하게 본 것 같다. 문제를 풀 때 전체를 보고 풀다가 몇 번 생각이 꼬였었다.

생각이 쉬워진 부분은 블럭이 '3 0 1 4'를 전체로 봤을 때 '3 0 4', '3 1 4'처럼 빗물이 들어갈 블럭을 가운데에 두고 좌우는 높이가 큰 블럭으로 두니 편했다. (개인적으로 알고리즘을 풀 때 창의력도 중요한 것 같다..)