[백준] 14719. 빗물 (JAVA)

🧺 빗물

 

조금 생각하기 어려운 구현 문제

 

---

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

 

 

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

 

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

 

---

🔑 IDEA

• 각 건물에 고인 물의 양을 계산해 더해 나간다.
• 더 큰 건물들 사이에 끼어 있으면 빗물이 고인다.
• 현재 인덱스에 고이는 빗물의 높이는, 왼쪽에서 가장 높은 건물과 오른쪽에서 가장 높은 건물 중 더 작은 값과 같다.

 

💡  나의 풀이

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

class Main {
	static int H;
	static int W;
	static int[] height;
	static int sum = 0;

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

		H = Integer.parseInt(st.nextToken());
		W = Integer.parseInt(st.nextToken());
		height = new int[W];

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

		rain();
		System.out.println(sum);
	}

	private static void rain() {
		for(int i=1; i<W-1; i++) {
			int left = 0;
			int right = 0;

			for(int j=0; j<i; j++) {
				left = Math.max(left, height[j]);
			}

			for(int j=i+1; j<W; j++) {
				right = Math.max(right, height[j]);
			}

			if(left > height[i] && right > height[i]) {
				sum += Math.min(left, right) - height[i];
			}
		}
	}
}

 

 

---

 

14719번: 빗물