[백준 14719] 빗물 (자바)

백준 14719번 빗물 (자바)

(2020 하반기 NHN 2번 문제와 유사)

 

 

출처

www.acmicpc.net/problem/14719

14719번: 빗물

 

 

 

문제

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

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

 

 

 

 

입력

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

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

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

 

 

 

출력

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

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

 

 

 

입출력 예

입출력 예 1

입출력 예 2

입출력 예 3

 

 

접근 방법

1. 현재를 기준으로 왼쪽과 오른쪽의 높이를 구하기 위해 1부터 반복문을 시작한다.

2. 현재를 기준으로 왼쪽과 오른쪽의 최대 높이를 구한다.

3. 현재가 왼쪽 최대높이와 오른쪽 최대 높이보다 낮으면 둘 중 낮은 높이에서 자신의 높이를 뺀다.

4. 3을 반복한다.

 

 

 

내 코드

package guhyun;

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

public class RainWater {
	private static int h, w;
	private static int[] block;
	private static int left, right, center;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input = reader.readLine().split(" ");
		
		h = Integer.parseInt(input[0]);
		w = Integer.parseInt(input[1]);
		
		block = new int[w];
		
		input = reader.readLine().split(" ");
		for (int i=0; i<w; i++) {
			block[i] = Integer.parseInt(input[i]);
		}
		
		left = center = right = 0;
		
		//가운데 기준으로 왼쪽 오른쪽 큰 친구를 찾는다.
		for (int i=1; i<w-1; i++) {
			left = right = 0;
			//i기준 왼쪽 중 제일 높은 친구 찾기
			for (int j=0; j<i; j++) {
				left = Math.max(left, block[j]);
			}
			
			//i기준 오른쪽 중 제일 높은 친구 찾기
			for (int j=i+1; j<w; j++) {
				right = Math.max(right, block[j]);
			}
			
			//현재 block이 left와 right보다 작으면 더해주기
			if (block[i] < left && block[i] < right) {
				center += Math.min(left, right) - block[i];
			}
			
		}
		
		System.out.println(center);
	}
	
	
}

 

 

 

고려할 점

1. 어떤 기준으로 왼쪽과 오른쪽을 기준으로 만들지 생각할 것