[백준] 14719 - 빗물

[문제링크]

14719번: 빗물

0. 위 그림과 같이 높이를 하나씩 받으며 스택에 저장하고, 해당 입력으로 인해 발생한 빗물 공간을 구해 누적한다

 

1. 입력 x가 들어왔을때, 스택에 자기보다 작은 값이 있다면, 빗물 공간이 발생할 수 있다

• 위 그림처럼 6 0 4 0 3 0 0 5 순으로 입력이 들어왔을때, 3과 5 사이에는 공간이 발생한다 (빨강)
• 그 다음 4와 5 사이에도 공간이 발생했는데, 이전에 3까지의 높이는 처리했으므로 4 높이에 대해서만 공간이 생긴다 (노랑)
• 이전에 처리한 높이를 prevCnt로 저장, 사용한다
• 공간이 계속해 발생할 수 있으므로, 스택을 계속 따라간다

 

2. 스택에 자기보다 큰 값이 있다면, 역시 공간이 발생할 수 있다

• 6과 4 사이에서 공간이 발생한다 (파랑)
• 이때 생성되는 공간의 높이는 입력 x에서 이전 처리값 prevCnt를 뺀 값이다
  • 위 그림에서 초록색 부분은, 입력 x는 5이고 prevCnt는 4이므로 높이는 1이다
• 자기보다 큰 값을 만났으므로, 공간이 계속해서 발생할 수 없으니 종료한다

 

3. 위 방식으로 공간의 높이는 구할 수 있다

• 공간의 너비를 구하기 위해, 스택에 저장할 때 값뿐 아닌 해당 지점의 x좌표도 함께 저장한다
• 두 좌표를 비교해 너비를 구하여, 높이와 곱해 총 빗물 공간의 면적을 구한다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int H = pint(st.nextToken());
		int W = pint(st.nextToken());
		
		st = new StringTokenizer(br.readLine(), " ");
		
		Stack<int[]> stack = new Stack<>();
		int area=0;
		
		for (int i = 0; i < W; i++) {
			int input = pint(st.nextToken());
			
			int prevMax=0, sum=0;
			while(!stack.isEmpty() && stack.peek()[0]<=input) {
				int[] tmp = stack.pop();
				
				if(tmp[0]>prevMax) {
					int height = tmp[0]-prevMax;
					prevMax=tmp[0];
					sum+= height*( i-tmp[1]-1 );
				}
				
			}
			
			if(!stack.isEmpty()) {
				int[] tmp = stack.peek();
				int height = input - prevMax;
				sum+= height*(i-tmp[1]-1);
			}
			
			area+=sum;
			// 스택에 넣기
			stack.add(new int[] {input,i});
			
		}
		System.out.println(area);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면