백준/14719/Java - 빗물

문제

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

14719번: 빗물

---

블록의 높이를 입력 받을 때마다 스택을 활용해 처리해보려는 생각을 했다.

 

빗물이 고이기 위해서는 블럭이 열리는 블럭(시작)과 닫히는 블럭(끝)이 있어야 하므로

처음 0이 아닌 블럭이 나오면 그 높이를 기준  int std로 놓고, 기준보다 작은  블럭이 오면  스택에 쌓는 식으로 로직을 구성해보았다.

그러다가 기준보다 큰  블럭이 나오면 그 블럭이 웅덩이를 완성시키는 끝 블럭이므로 스택에서 물이 고인 블럭들을 빼내면서 물의 양을 

계산하면 될 것이라는 생각이었다. 

위의 아이디어를 바탕으로 짠 코드는 다음과 같다.

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

public class Main {
	/*
	틀린 코드
  반례
  100 18
	28 100 43 33 37 100 87 15 52 35 54 86 60 24 99 56 4 40
	answer : 602
	*/
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int arr[] = new int[W];
		int sum = 0;
		boolean isStart = false;
		int std = 0;
		st = new StringTokenizer(br.readLine(), " ");
		Stack<Integer> stack = new Stack<>();

 		for(int i=0; i<W; i++) {
 			arr[i] = Integer.parseInt(st.nextToken());
 			//맨 처음 나오는 블록 체크. 
 			if(stack.isEmpty() && !isStart && arr[i] > 0) {
 				isStart = true;
 				std = arr[i];
 				continue;
 			}
			if(std > arr[i]) {
            	//4 1 2 1 처럼, 열리는 블럭보다 닫히는 블럭이 작은 경우는 마지막 블럭이 그 앞 블럭보다 작을 때
				if(!stack.isEmpty() && stack.peek() > arr[i] && i == W-1) { 
					std = stack.pop();
					while(!stack.isEmpty()) {
						sum += std - stack.pop();
					}
				}
				stack.push(arr[i]);
				
			}
			else if(std == arr[i]) {
				while(!stack.isEmpty()) {
					sum += std - stack.pop();
				}
			}
			else if(std < arr[i]) {
				while(!stack.isEmpty()) {
					sum += std - stack.pop();
				}
				std = arr[i];
			}
			System.out.println("i : " + i);
			System.out.println(sum);
			System.out.println(std);
			System.out.println("==============");
 		}
 		
 		if(stack.size() > 1) {
 			int last = stack.pop();
 			if(last > stack.peek()) {
 				std = Math.min(std, last);
 				while(!stack.isEmpty()) {
 					sum += std - stack.pop();
 				}
 			}
 		}
 		sb.append(sum);
 		System.out.println(sb);
 		
	}
}

 

문제에서 주어진 예시 입력들을 넣어봤을 때, 정답이 나와 제출을 해보았지만 결과는 틀렸습니다. 

질문 게시판을 살펴보다가 반례를 발견했다. 다시 코드를 살펴보니 100 ~ 100 구간까지는 정확하게  계산하지만,

100-99 구간에는 기준 높이가 업데이트 되지 않고 100으로 유지된다.

코드를 짜면서 생각한 것이지만 위의 방식은 경우의 수가 지나치게 세분화되어 있다보니 너무 복잡하다.

왜 대부분의 풀이가 배열로 다 받은 뒤, 좌우 양쪽 높이를 구해서  물의 높이를 구하는 지 알 수 있었다.

 

아무튼 위의 풀이 및 다른 사람들의 풀이를 참고하여 정리한 다음과 같다.

-> 쌓이는 물의 양이 결정되기 위해서는 좌우 양쪽 높이가 결정되어야 한다.

-> 블럭의 높이를 하나씩 받아서 처리하면 좌우 양쪽 높이를 결정하기 복잡하다.

-> 블럭을 돌면서, 왼쪽에서 가장 높은 블럭의 높이와 오른쪽에서 가장 높은 블럭의 높이를 구한다.

-> 두 높이중 작은 쪽과 자신의 높이의 차이만큼 물이 쌓인다.

-> 처음과 끝 블럭에는 물이 쌓일 수 없다.

 

이를  구현한 코드는 다음과 같다.

 

---

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int H = Integer.parseInt(st.nextToken());
		int W = Integer.parseInt(st.nextToken());
		int arr[] = new int[W];
		int sum = 0;
		
		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 curBlock = arr[i];
			int rMax = 0; 
			int lMax = 0;
			//왼쪽에서 가장 높은 블럭을 찾는다. 
			for(int j=0; j<i; j++) {
				lMax = Math.max(lMax, arr[j]);
			}
			//오른쪽에서 가장 높은 블럭을 찾는다. 
			for(int j=i+1; j<W; j++) {
				rMax = Math.max(rMax, arr[j]);
			}
			
			//현재 블럭위에 물이 고이려면, 왼쪽에서 가장 높은 블럭, 오른쪽에서 가장 높은 블럭보다 현재 블럭의 높이가 낮아야 한다.
			//위 조건을 만족한다면, 두 높이 중 낮은 높이와 현재 블럭 높이의 차 만큼  물이 고이게 된다. 
			if(curBlock < rMax && curBlock < lMax) {
				sum += Math.min(rMax, lMax) - arr[i];
			}
		}
 		sb.append(sum);
 		System.out.println(sb);
 		
	}
}