[백준 14719번 / 빗물 / JAVA / 투포인터]

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

14719번: 빗물

 

문제 접근

가로 길이와 크기가 같은 배열을 만들고 각 인덱스에 높이를 지정

각 인덱스를 돌면서 각 인덱스 기준으로 왼쪽의 가장 큰 높이와 오른쪽의 가장 큰 높이를 찾는다.

그럼 그 사이 공간에 빗물이 고이며 빗물은 최소한 가장 큰 높이인 왼쪽, 오른쪽 중 작은 숫자에서 각 인덱스의 높이를 뺀 만큼은 차게 된다.

이렇게 모든 인덱스를 돌면서 해당 인덱스마다 고이게 되는 빗물을 탐색 후 통합

 

→ 인덱스를 돌면서 인덱스 기준 왼쪽 최대 높이, 오른쪽 최대 높이(투 포인터) 찾기

유연한 사고력을 가지자

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int H = Integer.parseInt(st.nextToken()); // 세로
		int W = Integer.parseInt(st.nextToken()); // 가로
		
		st = new StringTokenizer(br.readLine());

		int[] height = new int[W]; // 인덱스 별 높이 지정
		for(int i=0; i<W; i++) height[i] = Integer.parseInt(st.nextToken());
		
		int rain = 0;
		
		for(int i=1; i<W-1; i++) { // 첫 인덱스와 마지막 인덱스엔 빗물이 고일 수 없다.
		   int leftHeight = 0;
		   int rightHeight = 0;
			
			for(int j=0; j<i; j++) {
				leftHeight = Math.max(height[j], leftHeight); // 현재 인덱스 기준 왼쪽 최고 높이 찾기
			}
			
			for(int j=(i+1); j<W; j++) {
				rightHeight = Math.max(height[j], rightHeight); // 현재 인덱스 기준 오른쪽 최고 높이 찾기
			}
			
			// 빗물이 고이기 위해선 현재 인덱스의 높이가 왼쪽 최고 높이와 오른쪽 최고 높이보다 작아야한다.
			// 빗물은 왼쪽, 오른쪽 중 최소 높이만큼은 찬다.
			if(height[i] < leftHeight && height[i] < rightHeight) rain += Math.min(leftHeight, rightHeight) - height[i];
		}
		System.out.println(rain);
	}
}