백준 js - 6198번

 

<문제>

https://www.acmicpc.net/problem/6198

 

 

 

<문제 핵심>

1. 스택을 이용하여 현재의 건물 높이보다 낮은 건물들은 스택에서 제거하게 되는데(stack.pop() ) 결론적으로 스택에 남는 것은 볼 수 있는 건물의 수가 담겨져 있을 것(ex.  스택에 10 7 4가 담기고 12가 들어올 때 10 7 4는 모두 12보다 높이가 작기 때문에 스택에서 제거해준다. 그럼 스택은 비어있게 되고 이때의 스택의 크기는 0이다 -> 이후 result에 스택의 크기를 더 해줄텐데 스택의 크기는 0이므로 result 값(4)이 그대로 유지된다.)

 

 

<문제 풀이과정 및 순서도>

1.  먼저 입력으로 주어진 건물의 높이를 받아오고 스택을 사용하여 각 건물에 대해 오른쪽으로 탐색하면서 스택을 이용해 자신보다 높이가 낮은 건물들을 관리한다.

 

 

2. 각 건물에서 스택의 길이를 결과에 더해주면서, 볼 수 있는 건물의 수를 계산하고 출력해준다.

 

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

const n = +input.shift();
const height = input.map(Number);

let stack = [];
let result = 0;

for (let i = 0; i < n; i++) {
  // 현재 건물의 높이보다 낮은 건물들을 스택에서 제거
  while (stack.length > 0 && stack[stack.length - 1] <= height[i]) {
    stack.pop();
  }
  // 현재 스택에 남아 있는 건물들은 모두 현재 건물에서 볼 수 있는 건물들
  result += stack.length;
  // 현재 건물을 스택에 추가
  stack.push(height[i]); //일단 처음에 stack에 10이 푸쉬될것 -> i=1일때로 진입
}

console.log(result);