[Java] 백준 14719번 빗물

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

14719번: 빗물

 

문제

---

 

코드 리뷰

---

이번 문제는 map을 2차원으로 만들면 좀 어렵고(?) 귀찮은 문제로 변합니다.

그냥 현재 기준에서 왼쪽에 가장 큰 벽과 오른쪽의 가장 큰 벽을 비교 후 작은 벽 - 현재 벽을 구해서 계속 더해주면다면 쉽게 해결가능한 문제였습니다.

 

package BJ;

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

public class BJ_빗물 {
	static int H, W;
	static int[] wall;
	
	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());
		
		wall = new int[W];

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

	private static int rain() {
		int result = 0;
		for (int i = 1; i < W - 1; i++) { // 처음과 마지막은 계산 때문에 뛰움
			int now = wall[i]; // 현재 블록
			int prev = wall[i]; // 이전 블록 중 가장 큰 블록
			int next = wall[i]; // 다음 블록 중 가장 큰 블록
			
			for (int j = i - 1; j >= 0; j--) { // 현재 블록의 왼쪽부터 시작
				if(wall[j] > now) { // 블록의 크기가 현재보다 크다면
					prev = Math.max(prev, wall[j]); // prev에 더 큰 값을 저장
				}
			}
			
			for (int j = i + 1; j < W; j++) { // 현재 블록의 오른쪽부터 시작
				if(wall[j] > now) { // 블록의 크기가 현재보다 크다면
					next = Math.max(next, wall[j]); // next에 더 큰 값을 저장
				}
			}
			
			if(Math.min(prev, next) > now) { // 현재 블록보다 왼쪽, 오른쪽 블록이 더 크다면
				result += (Math.min(prev, next) - now); 
                // 왼쪽과 오른쪽 중 작은것과 현재 블록을 뺌
			}
			
			
		}
		return result;
		
	}

}

 

Ysik Github : https://github.com/Y1sik/Algorithm/blob/main/BJ/BJ_%EB%B9%97%EB%AC%BC.java