[백준] 탑 보기 #22866
설명
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++ 풀이
추후 작성 예정
Author And Source
이 문제에 관하여([백준] 탑 보기 #22866), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ahu8867/백준-탑-보기-22866저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)