[ 백준 ] 14719 빗물

📌 Problem

2차원 세계에서 각 column에 대한 블록 높이가 주어졌을 때 빗물이 고이는 영역의 수를 구하면 된다. 빗물이 고이기 위해서는 고인 영역이 좌우로 블록으로 쌓여있어야 한다.

📌 Solution

각각의 높이별로 몇개의 구역에 빗물이 고일 수 있는지 확인하면 된다. 하나의 높이에 다음과 같이 높이가 있다고 생각해보자.

위의 상황에서 빗물이 고일 수 있는 블럭은 3, 4번째 칸과 6, 7, 8번째 칸이다. 결과적으로 해당 높이에서 빗물이 고일 수 있는 칸은 5칸이다. 각각의 높이에 대해서 빗물이 고일 수 있는 칸을 구하면 된다.

📌 Code

StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int H = Integer.parseInt(tokenizer.nextToken());
int W = Integer.parseInt(tokenizer.nextToken());
int[] heights = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int water = 0;
while (H > 0) {
    for (int i = 0; i < W; i++) {
        if (heights[i] >= H) {
            for (int j = i + 1; j < W; j++) {
                if (heights[j] >= H) {
                    water += j - i - 1;
                    i = j - 1;
                    break;
                }
            }
        }
    }
    H--;
}
result.append(water);