[JavaScript] 백준 빗물 (JS)

빗물

📚 문제 설명

2차원 세계에 블록이 있다.
이 세계에 비가 왔을 때 물이 고이는 양을 구하라.

예를 들어 아래에서 1이 블록이라고 가정하면 빗물은 0의 영역에 고이게 된다.

1
1 0 1
1 1 1

👨🏻‍💻 풀이 과정

풀이 과정은 생각보다 간단하다.
블록을 순차적으로 돌며, 현재 위치 기준 왼쪽 최댓값 left, 오른쪽 최댓값 right 를 비교하면 된다.

전체 로직은 아래와 같다.

• 현재 기준 좌측 최댓값 left, 오른쪽 최댓값 right 비교.
• 둘 중 더 작은 값과 현재 높이 차이 계산.
  • 만약 높이 차이가 음수가 되면 현재 높이가 더 크다는 뜻.
  • 음수라면 해당 위치의 고이는 물은 0.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, M] = input.shift().split(' ').map(Number);
    input = input[0].split(' ').map(Number);
	// 고인 물의 양.
    let answer = 0;
	// 좌측 블록부터 순차적으로 확인.
    for (let i = 0; i < input.length; i++) {
      	// 좌측 최댓값
        let left = 0;
      	// 우측 최댓값
        let right = 0;
      	// 좌측 최댓값 계산
        for (let j = 0; j < i; j++) {
            if (input[j] > left) left = input[j];
        }
      	// 우측 최댓값 계산
        for (let j = i + 1; j < input.length; j++) {
            if (input[j] > right) right = input[j];
        }
      	// min을 이용해 좌측, 우측 중 더 낮은 값과 현재 위치 비교.
      	// max를 이용해 음수가 나오면 0을 더해줌.
        answer += Math.max(Math.min(left, right) - input[i], 0);
    }
    console.log(answer);

!https://velog.velcdn.com/images/dannysir/post/252a7b63-1c6c-4b86-b0d4-788d8489be7b/image.png

🧐 후기

마지막 음수를 처리하는 과정 때문에 좀 고민이 되었던 문제였다.