2차원 세계에서 각 column에 대한 블록 높이가 주어졌을 때 빗물이 고이는 영역의 수를 구하면 된다. 빗물이 고이기 위해서는 고인 영역이 좌우로 블록으로 쌓여있어야 한다.
각각의 높이별로 몇개의 구역에 빗물이 고일 수 있는지 확인하면 된다. 하나의 높이에 다음과 같이 높이가 있다고 생각해보자.
위의 상황에서 빗물이 고일 수 있는 블럭은 3, 4번째 칸과 6, 7, 8번째 칸이다. 결과적으로 해당 높이에서 빗물이 고일 수 있는 칸은 5칸이다. 각각의 높이에 대해서 빗물이 고일 수 있는 칸을 구하면 된다.
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);