baekjoon_14719_빗물 java

java로 작성하였습니다.
java를 급하게 쓰게 되는 바람에 비효율적인 부분이 많을 수 있습니다..

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

package 구현;

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st=new StringTokenizer(br.readLine());

		int H=Integer.parseInt(st.nextToken());
		int W=Integer.parseInt(st.nextToken());
		int []map=new int[W];
		st=new StringTokenizer(br.readLine());
		int before=0;
		int after=0;
		for(int i=0;i<W;i++) {
			map[i]=Integer.parseInt(st.nextToken());
		}
		//입력
		for(int i=0;i<W;i++) {
			before+=map[i];
		}
		//---핵심
        
		int []lmax = new int[W];
		int []rmax = new int[W];
		
		lmax[0]=map[0];
		for(int i=1;i<W;i++) {
			lmax[i]=Math.max(map[i], lmax[i-1]);
		}
		
		rmax[W-1]=map[W-1];
		for(int j=W-2;j>=0;j--) {
			rmax[j]=Math.max(map[j], rmax[j+1]);
		}
		
		for(int k=0;k<W;k++) {
			after+=Math.min(lmax[k], rmax[k]);
		}

		System.out.println(after-before);
		
	}

}

한번풀면 머리에서 잊을 수 없는
어려워보이지만 알고나면 쉬운 그런 문제입니다.

간단히 알고리즘을 표현하면 더 큰 수를 만날때까지 현재 만난 큰 수로 길이를 세는 것입니다.
그런데 문제 예제와 같이 중간에 큰수가 오고 그 이후로 그 보다 작은수아래로 유지된다면 빗물이 고이는 특성상 작은 수에 초점이 맞춰져 빗물이 고이기 때문에 좌측과 우측에서 스캔을 한 뒤 그 둘의 min값을 구해야합니다.