[백준] 14719 빗물 - 구현 + 시뮬레이션 JAVA

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

14719번: 빗물

코드설명

구현과 시뮬레이션을 활용하는 문제입니다.

 

문제로직입니다.

1. 맨 첫번쨰 공간, 맨 마지막 공간에는 물이 고일 수 없습니다. (첫번째 공간에는 왼쪽벽이 없고, 마지막 공간에는 오른쪽벽이 없음)
2. 각 공간마다의 높이를 구해나갑니다. 이 문제에서 가장 중요한 점은, 왼쪽의 최대벽 높이와, 오른쪽의 최대벽 높이를 각각의 벽마다 구한뒤, 왼쪽의 최대벽 높이와 오른쪽의 최대벽 높이의 최소값을 더해주면 해당 벽에 고일 수 있는 물의 양이 구해집니다.

 

코드에 자세한 주석을 정리해보았습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int H, W;
	public static int[] arr;
	public static int answer = 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());
    
    	arr = new int[W];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<W;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	for(int i=1; i<W-1; i++) { //맨 첫번째 공간, 맨 마지막 공간에는 각각 왼쪽과 오른쪽에 벽을 세울수 없으므로 물을 채울 수 없습니다. 
    		int currentHeight = arr[i];
    		int leftMaxHeight = currentHeight;
    		int rightMaxHeight = currentHeight;
    		for(int k=i-1; k>=0;k--) { //왼쪽 최대벽 높이를 탐색합니다.
    			if(leftMaxHeight < arr[k]) {
    				leftMaxHeight = arr[k];
    			}
    		}
    		
    		for(int k=i+1; k < W; k++) { //오른쪽 최대벽 높이를 탐색합니다.
    			if(arr[k] > rightMaxHeight) {
    				rightMaxHeight = arr[k];
    			}
    		}
    		
    		int shorterHeight = Math.min(leftMaxHeight, rightMaxHeight); // 왼쪽 최대높이와 오른쪽 최대높이 중 더 짧은 높이로 물이채워집니다.
    		if(shorterHeight > currentHeight) { //만약 현재 벽보다 양옆의 벽중 하나라도 더 작다면, 계싼하지 않음. 둘다 커야만 물이 차기에 계산처리
    			answer +=  shorterHeight - currentHeight;
    		}
    	}
    	System.out.println(answer);
    	
    }
       
}