[JS|구현 알고리즘] 백준 14719번. 빗물

---

 

입력과 출력

• 입력
  • 2차원 세계의 세로 길이 H (1 ≤ H ≤ 500)
  • 2차원 세계의 가로 길이 W (1 ≤ W ≤ 500)
  • 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 있는 배열 Arr
    • 형태 : 3 1 2 3 4 1 1 2
• 출력
  • 빗물이 고이는 칸의 개수

 

문제 풀이 로직

• 빗물이 고이는 칸의 개수를 어떻게 측정할 수 있을까?

 

• 먼저, 입력값인 H와 W, Arr를 이용하여 다음과 같이 새로운 배열을 만들었다. (checkArr)

 

• 만들어진 checkArr를 한 줄씩 보면서 0과 1에 따라 빗물이 고이는 칸을 계산하기로 하였다.

 

• 빗물이 고이는 칸 계산
  • 변수 설명 : 한 줄 col, 해당 줄의 인덱스 colidx, 줄 내의 각 숫자 num, 해당 숫자의 인덱스 idx 체크하고 있는지 확인하는 isCheck, 빗물 고이는 칸의 개수 cnt, 빗물 고이는 칸 누적합 acc
  • 경우 1. num이 1일 때
    • isCheck가 true일 때
      • cnt를 누적합 변수 acc에 저장하고, cnt를 0으로 초기화 한다.
    • isCheck가 false일 때
      • isCheck를 true로만 바꾸면 된다.
  • 경우 2. num이 0일 때
    • 간단하게도, num이 0일때에는 isCheck가 true일 때만 cnt를 1개씩 세면 된다.

전체 코드

let [[H, W], [...Arr]] = require('fs')
  .readFileSync(process.platform === 'linux' ? 'dev/stdin' : 'input.txt')
  .toString()
  .trim()
  .split('\\n')
  .map((v) => v.split(' ').map(Number))

let checkArr = Array.from(Array(H), () => Array(W).fill('0'))

Arr.map((num, idx) => {
  for (let h = H; h > 0; h--) if (h <= num) checkArr[h - 1][idx] = '1'
})

let acc = 0

checkArr.reverse().forEach((col) => {
  let isCheck = false
  let cnt = 0
  col.forEach((num, idx) => {
    if (num === '1') {
      if (isCheck) {
        acc += cnt
        cnt = 0
      } else isCheck = true
    } else isCheck && cnt++
  })
})

console.log(acc)