글 읽기 - 최대힙 문제 반례부탁드리겠습니다...

durjs144 1년 전 0

계속 틀렸다고 나오는데 반례가 도저히 생각이 나지 않습니다ㅠㅠ

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let answer = [];
const inputArr = [];
rl.on("line", function (line) {
  inputArr.push(line);
}).on("close", function () {
  solution(inputArr);
  console.log(answer.join("\n"));
  process.exit();
});

function solution(arr) {
  const numArr = arr.map((el) => +el);
  const heap = new MaxHeap();

  for (let i = 0; i < numArr.length; i++) {
    // console.log(heap);
    if (i === 0) continue;
    if (numArr[i] === 0) {
      if (heap.size() === 0) {
        answer.push(0);
      } else {
        const number = heap.pop();
        answer.push(number);
      }
    } else if (numArr[i] > 0) {
      heap.push(numArr[i]);
    }
  }
}

class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  size() {
    return this.heap.length - 1;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  push(value) {
    this.heap.push(value);

    let curIdx = this.heap.length - 1;
    let parIdx = Math.floor(curIdx / 2);

    while (curIdx > 1 && this.heap[curIdx] > this.heap[parIdx]) {
      this.swap(curIdx, parIdx);
      curIdx = parIdx;
      parIdx = Math.floor(curIdx / 2);
    }
  }

  pop() {
    // if (this.heap.length < 2) return 0;

    const max = this.heap[1];

    if (this.heap.length <= 2) this.heap = [null];
    else this.heap[1] = this.heap.pop();

    let curIdx = 1;
    let leftIdx = curIdx * 2;
    let rightIdx = curIdx * 2 + 1;

    if (!this.heap[leftIdx]) return max;
    if (!this.heap[rightIdx]) {
      if (this.heap[curIdx] < this.heap[leftIdx]) {
        this.swap(curIdx, leftIdx);
      }
      return max;
    }

    while (
      this.heap[leftIdx] > this.heap[curIdx] ||
      this.heap[rightIdx] > this.heap[curIdx]
    ) {
      const maxIdx =
        this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;

      this.swap(maxIdx, curIdx);

      curIdx = maxIdx;
      leftIdx = curIdx * 2;
      rightIdx = curIdx * 2 + 1;
    }
    return max;
  }
}

durjs144 1년 전 0

엇 위에

const readline = require("readline");

이게 빠진거 같네요.

이 코드 추가 후에 확인 부탁드릴게요..!

durjs144 1년 전 0

문제를 찾았습니다.

82번째 줄 while문 안에서 leftIdx와 rightIdx가 배열크기를 넘어가는지 확인을 하고 있지 않아서

만약 leftIdx만 있는 경우 rightIdx가 undefined가 들어오게 되어 삼항 연산자에서 leftIdx가 maxIdx가 되는게 아니라 rightIdx가 되는 오류가 있었습니다.

86, 87 번째 줄에 있는 코드 대신 아래 코드를 삽입해서 돌리면 잘 돌아갑니다!

      let maxIdx;

      if (!this.heap[rightIdx]) {
        maxIdx = leftIdx;
      } else {
        maxIdx = this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;
      }

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

최대힙 문제 반례부탁드리겠습니다...

durjs144 1년 전 0

durjs144 1년 전 0

durjs144 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말