[BOJ 14719] 빗물

문제

빗물

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

 

 

풀이

설명

고이는 빗물의 총량을 구하는 문제입니다.

 

두 가지 방법으로 풀어봤습니다.

 

첫 번째 풀이

현재 블록과 이전 위치의 블록 사이에 고이는 빗물 양을 구해 더하는 방식입니다.

 

스택을 이용합니다.

스택에는 블록들의 인덱스와 높이를 저장합니다.

 

수행 과정은 다음과 같습니다.

1. 스택이 비어있지 않은 경우, 다음 과정을 반복해 수행합니다.
   1. 현재 블록과 마지막 블록 사이에 고이는 빗물 양을 구해 총량에 더합니다.
   2. 마지막 블록의 높이가 현재 블록보다 작거나 같은 경우, 스택에서 제거합니다.
   3. 마지막 블록의 높이가 현재 블록보다 크거나 같은 경우, 반복문을 종료합니다.\
2.  스택에 현재 블록의 인덱스와 높이를 저장합니다.

 

두 번째 풀이

블록 별로 해당 위치에 고이는 빗물의 최대 높이를 구해 더하는 방식입니다.

 

각 블록마다 왼쪽 최대 높이와 오른쪽 최대 높이 중 더 낮은 값에서 현재 블록의 높이를 빼 빗물의 양을 구하고 총량에 더합니다.

 

예시 코드

첫 번째 풀이

function solution() {
  const [H, W] = input().split(" ").map(Number);
  const blocks = input().split(" ").map(Number);
  const stack = [];
  let totalWater = 0;

  for (let i = 0; i < W; i++) {
    const currentHeight = blocks[i];
    let lastFilledHeight = 0;

    while (stack.length) {
      const [lastIndex, lastHeight] = stack.at(-1);
      const waterWidth = i - lastIndex - 1;
      const waterHeight =
        Math.min(currentHeight, lastHeight) - lastFilledHeight;
      const amount = waterWidth * waterHeight;
      totalWater += amount;
      lastFilledHeight += waterHeight;

      if (lastHeight <= currentHeight) stack.pop();
      if (lastHeight >= currentHeight) break;
    }

    stack.push([i, currentHeight]);
  }

  return totalWater;
}

 

두 번째 풀이

function solution() {
  const [H, W] = input().split(" ").map(Number);
  const blocks = input().split(" ").map(Number);

  const leftMax = Array(W).fill(0);
  const rightMax = Array(W).fill(0);
  let totalWater = 0;

  let maxHeightLeft = blocks[0];
  for (let i = 0; i < W; i++) {
    maxHeightLeft = Math.max(maxHeightLeft, blocks[i]);
    leftMax[i] = maxHeightLeft;
  }

  let maxHeightRight = blocks[W - 1];
  for (let i = W - 1; i >= 0; i--) {
    maxHeightRight = Math.max(maxHeightRight, blocks[i]);
    rightMax[i] = maxHeightRight;
  }

  for (let i = 0; i < W; i++) {
    totalWater += Math.min(leftMax[i], rightMax[i]) - blocks[i];
  }

  return totalWater;
}