[Node.js] 백준 22866 - 탑 보기

이거 왜 어렵지?

진짜 왜 어렵지?

왜 시간초과지?

예시 입력:
6
10 4 2 8 11 7

예시 출력:
1 4
1 1
0
2 5
2 4
1 5

접근

그냥 양쪽 다 확인하자 -> 시간초과

스택 두 번 나눠서 따로 돌리자 -> 오잉… 왜 됨..?

O(N^2)과 O(N)이 되어벌인..

핵심

  • buildings : 각 건물의 높이 저장된 곳
  • visibleCount : 각 건물에서 볼 수 있는 총 건물 개수
  • closestBuilding : 가장 가까운 건물 번호

코드

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .replace(/\r/g, "")
  .trim()
  .split("\n");

const N = parseInt(input[0]);

let buildings = input[1].split(" ").map(Number);

buildings = [0, ...buildings];

const visibleCount = Array(N + 1).fill(0);
const closestBuilding = Array(N + 1).fill(Infinity);

const st = []; // 스택

// 왼쪽에서 오른쪽으로 순회 (1번 건물부터 N번 건물까지)
for (let i = 1; i <= N; i++) {
  const currentHeight = buildings[i];

  while (st.length > 0 && st[st.length - 1][1] <= currentHeight) {
    st.pop();
  }

  if (st.length > 0) {
    visibleCount[i] += st.length;
    const [leftBuildingIdx, leftBuildingHeight] = st[st.length - 1];

    if (Math.abs(i - leftBuildingIdx) < Math.abs(i - closestBuilding[i])) {
      closestBuilding[i] = leftBuildingIdx;
    } else if (
      Math.abs(i - leftBuildingIdx) === Math.abs(i - closestBuilding[i])
    ) {
      closestBuilding[i] = Math.min(closestBuilding[i], leftBuildingIdx);
    }
  }
  st.push([i, currentHeight]);
}

// 스택 초기화
st.length = 0;

// 오른쪽에서 왼쪽으로 순회 (N번 건물부터 1번 건물까지)
for (let i = N; i >= 1; i--) {
  const currentHeight = buildings[i];

  while (st.length > 0 && st[st.length - 1][1] <= currentHeight) {
    st.pop();
  }

  if (st.length > 0) {
    visibleCount[i] += st.length;
    const [rightBuildingIdx, rightBuildingHeight] = st[st.length - 1];

    if (Math.abs(i - rightBuildingIdx) < Math.abs(i - closestBuilding[i])) {
      closestBuilding[i] = rightBuildingIdx;
    } else if (
      Math.abs(i - rightBuildingIdx) === Math.abs(i - closestBuilding[i])
    ) {
      closestBuilding[i] = Math.min(closestBuilding[i], rightBuildingIdx);
    }
  }
  st.push([i, currentHeight]);
}

let result = "";
for (let i = 1; i <= N; i++) {
  result += visibleCount[i];
  if (visibleCount[i] > 0) {
    result += ` ${closestBuilding[i]}`;
  }
  result += "\n";
}

console.log(result.trim());

결론

가끔은 나눠서 처리하자.

그리고 스택을 돌리면서 나보다 큰 것만 남기고 남은 요소들이 보이는 개수!

한국어 공부를 잘 해야 하는 문제.