[백준_14719] 빗물 ( Gold 5, by using JavaScript )

문제

이 문제의 대체재로 "LeetCode의 42. Trapping Rain Water" 를 푸셔도 무관합니다 :)

 

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

14719번: 빗물

 

How to Solve ?

 

[1] Two Pointer

 

전형적인 투포인터 문제로써,  [ left / right ] 포인터를 이동시키면 빗물의 양을 계산하는 문제이다.

 

왜 투포인터를 쓰는가? 생각해보면 [3,1,2] 이라는 인풋이 주어 지는 경우 

 

1 - 1) 3부터 시작

 

3부터 시작하는 경우 3 -1 => 2만큼의 물이 차있어야 할 것을 예상하지만 다음 기둥의 높이가 1이기에 2만큼의 물을 담을 수 없다.

 

이런 원리로 앞의 길이가 길어도 뒤의 길이가 짧으면 물을 담을 수 없기에 기둥의 크기를 비교하여 작은 값부터 연산을 하는 것이다.

 

 

function solution(height) {
  let answer = 0;
  let left = 0;
  let right = height.length - 1;
  let maxLeft = 0;
  let maxRight = 0;
 
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= maxLeft) {
        maxLeft = height[left];
      } else {
        answer += maxLeft - height[left];
      }
      left++;
    } else {
      if (height[right] >= maxRight) {
        maxRight = height[right];
      } else {
        answer += maxRight - height[right];
      }
      right--;
    }
  }
  return answer;
}
 
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split("\n");
const [H, W] = input[0].split(" ").map((x) => +x);
const height = input[1].split(" ").map((x) => +x);
// 테스트용 인풋
// let [N, K] = [4, 8];
// let height = [3, 1, 2, 3, 4, 1, 1, 2];
 
console.log(solution(height));

 

 Result