[백준]BOJ 14719 빗물(자바)

백준 14719 빗물 문제는 구현, 시뮬레이션 문제입니다.  

 

처음에 생각했을때 왼쪽->오른쪽, 오른쪽->왼쪽 이렇게 돌면서 왼쪽->오른쪽일때는 배열 0번 ~ W-1번 인덱스를 돌며 현재 블록 높이보다 큰 블록 높이를 찾아 이에 대한 차이를 계산하였고, 오른쪽->왼쪽 돌때도 배열 W-1 ~ 0번 인덱스를 돌며 현재 높이보다 큰 값을 찾아 차이를 계산해주었습니다.

 

이렇게 하니 문제 예시 테케 2개 정도는 맞았고, 1%에서 틀렸다라는 문구가 나왔습니다ㅠ

 

이후에 계속 생각해보았지만 도무지 모르겠어서, 결국 코드는 아니지만 어떤 로직으로 이루어졌는지 정답을 보았습니다ㅠ

 

 

 

로직

고인 빗물이 되기 위해서는 현재 인덱스를 기준으로 양쪽에 자신보다 큰 높이의 블록이 존재해야 합니다.

 

 

1. 현재 인덱스를 기준으로 왼쪽에 현재 높이보다 큰 높이를 찾는다.

2. 현재 인덱스를 기준으로 오른쪽에 현재 높이보다 큰 높이를 찾는다.

3. 1,2번을 통해 찾은 왼쪽, 오른쪽 높이 중에서 작은 높이를 찾습니다. Math.min(left 높이, right 높이)

4. 3번에서 찾은 높이 - 현재 높이를 통해 결과값에 더해줍니다.

 

 

 

 

구현 

public class Main_14719 {
	
	
	public static void main(String[] args) throws NumberFormatException, 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());//가로
		
		
		int[] maps = new int[W];
		int result = 0;
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < W; i++) {
			maps[i] = Integer.parseInt(st.nextToken());
		}
		
		
		int left = 0, right = 0;
		int min = 0;
		//양쪽에 현재 인덱스보다 높은 블록이 있어야 빗물이 고일 수 있다.
		for (int i = 1; i < W; i++) {
			left = maps[i];//현재 높이
			//왼쪽을 기준으로 현재 블록 높이보다 높은 높이 찾기
			for (int j = i-1; j >= 0; j--) {
				if(left < maps[j]) {
					left = maps[j];
				}
			}
			//오른쪽을 기준으로 현재 블록 높이보다 높은 높이 찾기
			right = maps[i];
			for (int j = i+1; j < W; j++) {
				if(right < maps[j]) {
					right = maps[j];
				}
			}
			min = Math.min(left, right);
			result += Math.abs(min-maps[i]);
		}
		System.out.println(result);
	}
	
	
}