[백준] 빗물 - JavaScript 풀이

오랜만에 알고리즘 문제 풀이를 다시 블로그에 올리게 된 이유가 두가지 있다.

첫번째로, 문제 풀고 더 나은 코드를 찾아보거나 고민하는 시간이 부족한 것 같아서이다.

 

골드 문제로 올라오니까 한 문제 풀이에도 오래 걸려서, 문제를 풀고 난 뒤에 시간을 많이 안들이게 되었다.

그러다보니 문제 풀이 방식도 한정적이고 더 티어 높아지면 못 푸는 문제가 너무 많아질 것 같았다.

여러 방식의 문제 풀이를 진행하고 블로그에 올리면 나도 제대로 이해하고 넘어갈 것 같다는 게 첫번째 이유다.

 

두번째로, 변수명을 좀 더 신경 쓰고 싶어졌다.

 

부트캠프 다니면서 문제 풀 때도 그렇고 프로젝트 할 때도 사실 변수명에 크게 신경을 안썼던 것 같다.

한번 풀고 말 알고리즘 문제는 특히.

그리고 변수명이 길면 안된다는 강박같은 게 있었는데, 며칠전 변수명명에 대해 찾아보다가 10 ~ 16자 사이 변수명이 디버깅하기 가장 좋다는 내용을 보고 변수명을 더 직관적으로 짓는 연습을 하려고 한다.

 

이런 이유에서 하루 한 문제씩 알고리즘 문제 풀이를 올려보려고 한다.

---

💙 문제 설명

 

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

 

 

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

💛 입력

 

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

 

💚 출력

 

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

 

---

❤️ 문제 풀이 방법

항상 문제들을 완전탐색으로 푸는 습관이 또 도졌다....

근데 H, W가 500이하라서 시간복잡도에는 안터졌다.

 

그래도 앞으로는 여러가지 방법으로 문제를 풀어보고 더 좋은 방식을 탐구해보고 싶어져서 알고리즘 풀이법을 적기로 했다.

 

1️⃣ 브루트포스 (완전탐색)

가장 먼저, 직관적으로 최대 height를 기준으로 height를 1씩 줄여가면서 넓이를 구하면 되겠다고 생각했다.

시간복잡도는, 문제 조건인 높이와 너비가 500이하라서 O(H * W)이다.

 

const fs = require("fs");
// TODO: 제출 시 경로 변환 필수 ("/dev/stdin")
const input = fs.readFileSync("test.txt", "utf8").toString().trim().split("\n");

function solution(input) {
  const [worldHeight, worldWidth] = input[0].split(" ").map(Number);
  let areaSum = 0;
  let maxHeight = -1;
  const blockHeightArray = input[1].split(" ").map((str) => {
    num = Number(str);
    maxHeight = Math.max(maxHeight, num);
    return num;
  });

  // 최대 높이가 0일 때까지 한층씩 계산
  while (maxHeight !== 0) {
    // maxHeight로 시작하는 startIndex
    let startIndex = -1;

    // 블록의 높이가 저장된 배열 순회
    for (
      let blockIndex = 0;
      blockIndex < blockHeightArray.length;
      blockIndex++
    ) {
      // 최대 높이보다 현재 블록의 높이가 같거나 더 높은 경우
      if (maxHeight <= blockHeightArray[blockIndex]) {
        if (startIndex === -1) {
          startIndex = blockIndex;
          continue;
        }

        areaSum += blockIndex - startIndex - 1;
        startIndex = blockIndex;
      }
    }

    maxHeight--;
  }

  return areaSum;
}

console.log(solution(input));

 

 

2️⃣ 투포인터

첫번째 방법으로 문제 풀이 후, 시간 복잡도를 더 줄일 방법을 고민해봤다.

인접 배열끼리 비교하는 것만 생각하니까 딱히 방법이 떠오르지 않아서 맞은 사람들의 코드를 살펴봤다.

투포인터 방법을 사용할 수 있는걸 생각 못했던게 조금 아쉬웠다.

 

투포인터 방식으로 문제 풀이하는 방법은 양 끝을 비교해서 둘 중 높이가 더 낮은 블록을 기준으로, 사이값들을 비교해 나가는 방식이다.

로직을 자세히 적어보면

 

1) 왼쪽의 높이가 더 낮으면

2) 지금까지의 높이들보다 높은지 판단하고, 맞다면 갱신한다

3) 지금까지의 높이들 중 가장 높지 않다면, 들어간 부분이니까 빗물이 고일 수 있으므로 최종 넓이에 더해준다

4) 포인터를 오른쪽으로 이동한다

 

const fs = require("fs");
// TODO: 제출 시 경로 변환 필수 ("/dev/stdin")
const input = fs.readFileSync("test.txt", "utf8").toString().trim().split("\n");

function solution(input) {
  const [worldHeight, worldWidth] = input[0].split(" ").map(Number);
  const blockHeight = input[1].split(" ").map(Number);
  let areaSum = 0;
  let [left, right] = [0, worldWidth - 1];
  let [maxLeftHeight, maxRightHeight] = [0, 0];

  // 왼쪽 인덱스보다 오른쪽 인덱스가 더 클 때 반복
  while (left < right) {
    // 왼쪽 포인터의 높이보다 오른쪽 포인터 높이가 더 큰 경우
    if (blockHeight[left] < blockHeight[right]) {
	  // 왼쪽의 값들 중 가장 큰 값과 비교
      if (maxLeftHeight <= blockHeight[left]) {
        maxLeftHeight = blockHeight[left];
      } else {
        // 들어간만큼 더해준다
        areaSum += maxLeftHeight - blockHeight[left];
      }
      left++;
    } else {
      if (maxRightHeight <= blockHeight[right]) {
        maxRightHeight = blockHeight[right];
      } else {
        areaSum += maxRightHeight - blockHeight[right];
      }
      right--;
    }
  }
  return areaSum;
}

console.log(solution(input));

 

문제 풀이에서 더 개선할 부분이 있거나, 좋은 변수명이 있으면 댓글로 남겨주시면 좋을 것 같습니다.