[백준] 14719번 빗물 - JS

문제 링크

난이도가 크게 어렵지 않은데도 불구하고 오랫동안 헤맨 문제이다..
직관적으로 생각하는 힘을 더 키워야겠다

문제 설명

문제 해설

아래의 그림과 함께 문제를 이해해보자

먼저 블록과 블록 사이에서만 빗물이 고일 수 있으니 가장 왼쪽과 가장 오른쪽에는 빗물이 고일 수 없다

따라서 2번째 열부터 7번째 열까지 확인하며 해당 열에 물이 얼마나 고일 수 있는지 확인하면 된다

2번째 열

2번째 열에 물이 얼마나 고일 수 있는지 확인해보자

2번째 열을 기준으로 좌우 블록들의 높이에 따라 고이는 물의 양이 달라질 것이다

1번째 블록의 높이가 3, 3번째 블록의 높이는 2로, 이 시점에서 한칸의 물이 고인다는 것을 직관적으로 알 수 있다

1번째 블록이 가장 좌측의 블록이니 그대로 두고, 4번째 블록을 보자

4번째 블록의 높이는 3으로 2번째 열에는 두칸의 물이 고일 수 있다

이제 범위를 1번째 블록에서 5번째 블록으로 옮겨보자

우측 블록의 높이가 4지만 좌측 블록의 높이가 3이기 때문에 여전히 2칸의 물이 고일 수 있다

즉 2번째 열을 기준으로 좌측으로 가장 높은 블록과 우측으로 가장 높은 블록을 찾은 후, 더 낮은 쪽의 높이와 2번째 열의 높이를 빼주면 고이는 물의 양을 알 수 있다
단, 2번째 열의 높이가 더 낮은 쪽의 높이와 같거나 클때에는 우뚝 솟아있는 모양으로, 빗물이 고일 수 없다

위의 과정을 코드로 작성하면 아래와 같다

🏁 정답 코드

function solution(H, W, block) {
  let amountOfWater = 0;

  for (let i = 1; i < W - 1; i++) {
    const leftMaxHeight = Math.max(...block.slice(0, i));
    const rightMaxHeight = Math.max(...block.slice(i + 1));
    const basisHeight = Math.min(leftMaxHeight, rightMaxHeight);

    if (block[i] < basisHeight) amountOfWater += basisHeight - block[i];
  }

  return amountOfWater;
}