[백준][BOJ-14719][자바] 빗물

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

14719번: 빗물

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int answer = 0;
		int[] rainBlock = new int[M];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			rainBlock[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=1; i<M-1; i++) {
			int[] leftArr = Arrays.copyOfRange(rainBlock, 0, i);
			int leftMax = Arrays.stream(leftArr).max().getAsInt();
			
			int[] rightArr =Arrays.copyOfRange(rainBlock, i, M);
			int rightMax = Arrays.stream(rightArr).max().getAsInt();
			
			int min = Math.min(leftMax, rightMax);
			if( rainBlock[i] >= min) continue;
			
			answer += min - rainBlock[i];
		}
		
		System.out.println(answer);
	}
}

정리

문제만 바로 이해한다면 빠르게 풀 수 있는 문제였습니다.

1. 블록을 저장하는 배열을 선언합니다.
2. 양쪽 끝은 무조건 값이 작든 많은 물이 고일 수가 없기 때문에 1부터 M-1까지 반복합니다.
3. 자기 자신에서 왼쪽에 제일 큰 값과 오른쪽의 제일 큰 값을 가져옵니다. 
4. 두 개의 값 중 작은 값이 해당 자리에서 빗물이 넘치지 않고 고일 수는 최대치입니다. 
5. 만약 해당 자리의 블록의 수가 min 보다 클 경우 고일 수가 없습니다.
6. 마지막으로 5번 조건에 만족 안 한다면 물이 고일 수 있기 때문에 min - 현재 블록 높이를 빼면 해당 자리에 고일 수 있는 빗물의 양입니다.

끝!