BOJ - 14719 ) 빗물

---

www.acmicpc.net/problem/14719

14719번: 빗물

---

모 기업 코딩테스트에서 출제되었던 문제이다. 

 

배열의 앞,뒤로 탐색하면서 나보다 큰 벽을 만났을때, 그 중간 벽들과의 차이를 더해준다.

 

시간복잡도 O(2*500)으로 처리가능하다

---

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

public class 빗물 {

	public static void main(String[] args) throws Exception {
		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 num[] = new int[w];
		st = new StringTokenizer(br.readLine());
		for(int i =0; i < w; i++) num[i] = Integer.parseInt(st.nextToken());
		
		int answer = 0;
		int s = 0;
		int maxidx = 0;
		
		for(int i=1 ; i < w ; i++) {
			if(num[i] >= num[s]) {
				if(i==s+1) {
					s =i;
					continue;
				}
				// i 부터 s 까지
				for(int j = s ; j < i ; j++) {
					answer += (num[s]-num[j]);
					num[j] = num[s];
				}
				s = i;
			}
		}
		
		s = w-1;
		for(int i= w-2; i>=0 ; i--) {
			if(num[i] >= num[s]) {
				if(i==s-1) {
					s =i;
					continue;
				}
				for(int j = s ; j > i ; j--) {
					answer += (num[s]-num[j]);
					num[j] = num[s];
				}
				s = i;
			}
		}
		System.out.println(answer);
	}
}

---