14719 빗물

문제

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

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

입력

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

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

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

출력

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

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

====

문제 풀이

빗물을 쌓는 방파제를 양 옆에 두고 그 중간지점에 위치한 기둥들의 높이들을 두개의 방파제 중 최소 높이를 가지는 방파제의 높이를 빼준 뒤 정답에 더해주면 되는 문제이다.

인덱스를 0부터 탐색해가면서 왼쪽 방파제, 중간 기둥들 ,오른쪽 방파제을 기록할 stack을 선언해준다.

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [h, w] = input[0].split(' ').map(Number);
const infos = input[1].split(' ').map(Number);

let answer = 0;
const stack = [];

stack 의 [0] 은 왼쪽 방파제가 될 것이고, 왼쪽 방파제보다 작은 값들은 중간 기둥들이 될 것이다.

그리고 왼쪽 방파제인 stack[0] 이상인 값은 오른쪽 방파제가 된다는 것을 생각하며 인덱스 0부터 마지막까지 탐색을 진행한다.

이 때 왼쪽 방파제보다 작은 값들을 stack에 넣어줬고, 오른쪽 방파제는 왼쪽 방파제 이상인 값이 되므로 

중간에 쌓일 빗물의 높이를 계산할 때는 방파제 중 작은 값은 왼쪽 방파제가 된다는 것을 감안하여 계산식을 만들고 최종 정답에 더해준다.

for (let i = 1; i < w; i++) {
    if (currentHeight < stack[0]) {
        stack.push(currentHeight);
    } else {
        const height = stack[0];
        stack.shift();
        while (stack.length) {
            const num = stack.shift();
            answer += height - num;
        }
        stack.push(currentHeight);
    }
}

위의 계산을 끝마치면 stack에는 왼쪽 방파제가 최대 높이가 되는 경우만 남게된다. 

(위에서는 왼쪽 방파제가 오른쪽 방파제보다 작은 경우만 계산했으므로)

이제 stack[0]이 제일 큰 방파제가 된 다는 것을 알고 있으므로 이것을 처리해주는 로직을 세운다.

왼쪽 방파제가 있다는 것을 알고 있으므로 stack의 끝자락부터 꺼내어보며 오른쪽 방파제들을 찾고 왼쪽 방파제가 나타날때까지 탐색을 진행. 오른쪽 방파제보다 큰 값이 나온다면 그것이 왼쪽 방파제가 됨과 동시에 새로운 오른쪽 방파제가 된다. 이것을 코드화 하면 아래와 같다.

if (stack.length) {
    let height = stack.pop();
    while (stack.length) {
        const num = stack.pop();
        if (num >= height) {
            height = num;
        } else {
            answer += height - num;
        }
    }
}

정답 코드 

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [h, w] = input[0].split(' ').map(Number);
const infos = input[1].split(' ').map(Number);

let answer = 0;
const stack = [infos[0]];
for (let i = 1; i < w; i++) {
    if (currentHeight < stack[0]) {
        stack.push(currentHeight);
    } else {
        const height = stack[0];
        stack.shift();
        while (stack.length) {
            const num = stack.shift();
            answer += height - num;
        }
        stack.push(currentHeight);
    }
}
if (stack.length) {
    let height = stack.pop();
    while (stack.length) {
        const num = stack.pop();
        if (num >= height) {
            height = num;
        } else {
            answer += height - num;
        }
    }
}

console.log(answer);