문제 개요

문제: 빗물

분류: 구현, 시뮬레이션

난이도: 골드5

문제 풀이

다른 사람 풀이를 참고했다.

현재 블록을 기준으로 왼쪽에 있는 블록 중 가장 높은 블록과 오른쪽에 있는 블록 중 가장 높은 블록을 찾는다.
그리고 둘 중 더 낮은 블록의 높이에서 현재 블록의 높이를 빼면 현재 블록 위로 고이는 물의 용량을 구할 수 있다.

단, 현재 블록의 높이가 왼쪽 오른쪽의 두 블록의 높이보다 높은 경우 음수가 나오기 때문에 예외처리 해주어야 한다.

아래 그림은 문제의 예제 입력 2를 예시로 풀이한 그림이다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let [HW, height] = fs.readFileSync(filePath).toString().trim().split("\n");

const solution = (HW, height) => {
  const [H, W] = HW.split(" ").map(Number);
  height = height.split(" ").map(Number);

  let answer = 0;

  for (let currBlock = 1; currBlock < W - 1; currBlock++) {
    let leftMaxHeight = 0;
    let rightMaxHeight = 0;

    // 현재 블록을 기준으로 왼쪽에 있는 블록 중 가장 높은 블록의 높이를 찾는다.
    for (let i = 0; i < currBlock; i++)
      leftMaxHeight = Math.max(leftMaxHeight, height[i]);
    // 현재 블록을 기준으로 오른쪽에 있는 블록 중 가장 높은 블록의 높이를 찾는다.
    for (let i = currBlock + 1; i < W; i++)
      rightMaxHeight = Math.max(rightMaxHeight, height[i]);

    // 현재 블록 위로 고인 빗물의 용량을 구한다.
    answer += Math.max(
      0,
      Math.min(leftMaxHeight, rightMaxHeight) - height[currBlock]
    );
  }

  console.log(answer);
};

solution(HW, height);