14179_빗물 (JAVA)

14719번: 빗물

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int sero = sc.nextInt();
		int garo = sc.nextInt();

		int[] block = new int[garo];
		int[] rain = new int[garo];
		for(int i=0; i<garo; i++){
			block[i] = rain[i] = sc.nextInt();
		}

		//왼->오 탐색
		Stack<Integer> stack = new Stack<>();
		int temp = block[0];
		for(int i=0; i<garo; i++){
			if(temp > block[i])
				stack.push(i);
			else{
				while(!stack.isEmpty()){
					int n = stack.pop();
					rain[n] = temp;
				}
				temp = block[i];
			}
		}
		stack.clear();

		//오->왼 탐색
		temp = block[garo-1];
		for(int i=garo-1; i>=0; i--){
			if(temp > block[i])
				stack.push(i);
			else{
				while(!stack.isEmpty()){
					int n = stack.pop();
					rain[n] = temp;
				}
				temp = block[i];
			}
		}
		stack.clear();

		//정답 추출
		int ans = 0;
		for(int i=0; i<garo; i++){
			ans += rain[i]-block[i];
		}
		System.out.println(ans);
	}
}

 

2304번 문제 변형이다. (두 문제 난이도가 왜 다른지 의문!!)

2304번과 다른 점 : 배열을 두개 만들어 입력받고, 배열 하나만 수정하고 나중에 두개 차이를 모두 더해 출력한다.

[백준] 2304_창고 다각형 (Silver2) (JAVA)