글 읽기 - node.js 틀렸다고 하네요 힙정렬 사용했고 테스트해보면 잘 뜨는데 ㅠ

zzalsrud 2년 전 0

<해결했습니다. - 0이 들어갔을 때 제대로 정렬이 안됐었는데 bubbleUp과 bubbleDown 메소드에서 0이 false로 간주되어서 정렬이 안됐었어서 this.parent(index) !== undefined 이렇게 고쳤더니 됐어요>

힙 이용해서 최소힙 만들어서 힙정렬로 풀었습니다

vscode로 테스트해보면 잘 정렬이 되는데 제출하면 2퍼센트 진행되다가 '틀렸습니다' 라고 나오네요.

출력도 join으로 해서 한 번에 출력했습니다

시간초과도 아니고 아예 틀렸습니다 라고 하니,, 대체 어느 부분이 잘못된건지 알 수가 없네요 ㅠㅠㅠㅠㅠ

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const size = Number(input[0]);
class Heap {
  constructor() {
    this.items = [];
  }
  //swap
  swap(index1, index2) {
    let temp = this.items[index1];
    this.items[index1] = this.items[index2];
    this.items[index2] = temp;
  }
  //parentIndex
  parentIndex(index) {
    return Math.floor((index - 1) / 2);
  }

  //leftChildIndex
  leftChildIndex(index) {
    return index * 2 + 1;
  }

  //rightChildIndex
  rightChildIndex(index) {
    return index * 2 + 2;
  }

  //parent
  parent(index) {
    return this.items[this.parentIndex(index)];
  }

  //leftChild
  leftChild(index) {
    return this.items[this.leftChildIndex(index)];
  }

  //rightChild
  rightChild(index) {
    return this.items[this.rightChildIndex(index)];
  }
}
class MinHeap extends Heap {
  //bubbleUp
  bubbleUp() {
    let index = this.items.length - 1;
    while (this.parent(index) && this.parent(index) > this.items[index]) {
      this.swap(index, this.parentIndex(index));
      index = this.parentIndex(index);
    }
  }

  //bubbleDown
  bubbleDown() {
    let index = 0;
    while (
      this.leftChild(index) &&
      (this.leftChild(index) < this.items[index] ||
        this.rightChild(index) < this.items[index])
    ) {
      let smallerIndex = this.leftChildIndex(index);
      if (
        this.rightChild(index) &&
        this.rightChild(index) < this.items[smallerIndex]
      ) {
        smallerIndex = this.rightChildIndex(index);
      }
      this.swap(index, smallerIndex);
      index = smallerIndex;
    }
  }

  //add
  add(item) {
    this.items[this.items.length] = item;
    this.bubbleUp();
  }
  //poll
  poll() {
    let item = this.items[0];
    this.items[0] = this.items[this.items.length - 1];
    this.items.pop();
    this.bubbleDown();
    return item;
  }

  //sort
  sort() {
    let sort = [];
    const count = this.items.length;
    for (let i = 0; i < count; i++) {
      sort.push(this.poll());
    }
    return sort;
  }
}

const minheap = new MinHeap();
for (let i = 1; i <= size; i++) {
  minheap.add(Number(input[i]));
}
console.log(minheap.sort().join("\n"));

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

문제

문제

출처

ICPC

node.js 틀렸다고 하네요 힙정렬 사용했고 테스트해보면 잘 뜨는데 ㅠ

zzalsrud 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말