[백준 14719번] 빗물 - 자바스크립트(nodejs)

 

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

14719번: 빗물

const fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().trim().split('\n');
const height = +input[0][0];
input = input[1].split(' ').map(Number);

let answer = 0;

for (let i = 1; i < input.length; i++) {
  let left = -1;
  let right = -1;
  let min = 0;
  let result = 0;

  for (let j = i; j >= 0; j--) {
    left = Math.max(left, input[j]);
  }

  for (let j = i; j < input.length; j++) {
    right = Math.max(right, input[j]);
  }

  min = Math.min(left, right);
  result += min - input[i];
  answer += result;
}

console.log(answer);

간단하게 현재 인덱스 기준으로 왼쪽에서 가장 큰 기둥, 오른쪽에서 가장 큰 기둥을 찾아 최소값을 찾은 뒤 빼주면 된다.

 

4 2 2 3 5 이렇게 주어졌다고 쳐보자.

				ㅇ
ㅇ				ㅇ
ㅇ			ㅇ	ㅇ
ㅇ	ㅇ	ㅇ	ㅇ	ㅇ
ㅇ	ㅇ	ㅇ	ㅇ	ㅇ

     0           1           2          3           4

 

 

1번 째, 2번 째 인덱스

왼쪽 최대값 = 4 / 오른쪽 최대값 = 5  => 최소값은 4이므로 2를 더해준다.

 

3번 째 인덱스

왼쪽 최대값 = 4 / 오른쪽 최대값 = 5  => 최소값은 4이므로 1을 더해준다.

 

 

문제를 생각하며 좌 우에 기둥이 더 큰 게 있으면 어떡하지 라는 생각을 했지만, 고인 개수를 세는거라 최소값을 이용하면 쉽게 풀 수 있었다.