[백준] 탑 보기 #22866

welchs·2022년 1월 30일
0

알고리즘

목록 보기
28/44
post-thumbnail

설명

stack을 두 개 사용해서 푸는 문제
정방향, 역방향으로 스택을 사용해서 현재 위치 기준으로 높은 것들의 집합의 개수를 더해준다. 그리고 자기 자신을 추가해서 이후에 찾는 빌딩의 높이가 더 낮을 경우 자기 자신도 더 높은 빌딩에 추가되므로 이렇게 계산한다.
마지막으로 빌딩 사이의 거리가 낮을 수록 우선순위를 줘서 문제 출력 요구사항에 맞춰준다.

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const buildings = input[1].split(' ').map(Number);

const solution = (N, buildings) => {
  const countArr = new Array(N).fill(0);
  const closestArr = [];
  const frontStack = [];
  const backStack = [];
  for (let i = 0; i < buildings.length; i++) {
    const height = buildings[i];
    while (frontStack.length && frontStack[frontStack.length - 1][1] <= height)
      frontStack.pop();
    if (frontStack.length) {
      countArr[i] += frontStack.length;
      closestArr[i] = {
        no: frontStack[frontStack.length - 1][0],
        dist: i - frontStack[frontStack.length - 1][0],
      };
    }
    frontStack.push([i, height]);
  }
  buildings.reverse();
  for (let i = 0; i < buildings.length; i++) {
    const height = buildings[i];
    while (backStack.length && backStack[backStack.length - 1][1] <= height)
      backStack.pop();
    if (backStack.length) {
      countArr[N - i - 1] += backStack.length;
      if (
        !closestArr[N - i - 1] ||
        backStack[backStack.length - 1][0] - N + i + 1 <
          closestArr[N - i - 1].dist
      ) {
        closestArr[N - i - 1] = {
          no: backStack[backStack.length - 1][0],
          dist: backStack[backStack.length - 1][0] - N + i + 1,
        };
      }
    }
    backStack.push([N - i - 1, height]);
  }
  return countArr
    .map((v, idx) => (v === 0 ? v : `${v} ${closestArr[idx].no + 1}`))
    .join('\n');
};

console.log(solution(N, buildings));

C++ 풀이

추후 작성 예정
profile
고수가 되고 싶은 조빱

0개의 댓글