[백준] 2751. 수 정렬하기 2 (node.js/javascript/자바스크립트/정렬/힙정렬/알고리즘/코딩테스트)

 

---

내가 작성한 코드 (자바스크립트)

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)];
  }

  //peek
  peek() {
    return this.items[0];
  }

  size() {
    return this.items.length;
  }
}
class MinHeap extends Heap {
  //bubbleUp
  bubbleUp() {
    let index = this.items.length - 1;
    while (
      this.parent(index) !== undefined &&
      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) !== undefined &&
      (this.leftChild(index) < this.items[index] ||
        this.rightChild(index) < this.items[index])
    ) {
      let smallerIndex = this.leftChildIndex(index);
      if (
        this.rightChild(index) !== undefined &&
        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"));

자바스크립트의 내장함수인 sort()로 정렬하지 않고 힙정렬을 이용해서 풀어보았다.

input이 최대 1,000,000(백만)까지 이기 때문에 시간복잡도가 O(nlog(n))인 힙정렬로 풀어보았다.

 

하나 내가 실수한 것은, 예전에 힙정렬을 공부했었을 때는 양수 데이터만 넣어보았어서 그때는 문제없이 돌아갔기 때문에

예제만 돌려보고 잘 돌아가서 제출했는데 대뜸 '틀렸습니다' 라고 떠서 당황스러웠다.

vscode에서 혼자 테스트해보았을 때는 됐는데 '시간초과'도 아니고 '틀렸습니다' 라고 뜨니 어떻게해야할지 감을 못잡았는데

혹시 몰라서 문제를 다시 읽어보니 입력값은 절댓값이 1,000,000보다 작거나 같은 정수라고 했으므로 음수나 0도 포함이 되길래 음수도 넣어보고 0도 넣어보니 음수는 문제가 없었으나 0이 포함되면 정렬이 제대로 되지 않는 것을 발견했다.

 

그 부분을 한번 확인해본 결과 내가 작성한 힙 클래스에서 bubbleUp과 bubbleDown 부분에서 while문을 돌 때 예를 들어 bubbleUp의 경우 부모노드가 존재하고 - 부모 노드의 값보다 작다면 반복문을 실행하도록 작성했었는데, 여기서 부모노드가 존재한다는 부분을 단순히 this.parent(index)로 해버리니 난 당연히 그 안에 값이 있다면 true로 간주될 줄 알았으나, 실제로 값이 0이 들어가는 경우에는 false로 간주되어 this.parent(index)가 존재하지 않는 것처럼 되어버려서 반복문을 돌지 않기 때문에 0이 등장하는 부분부터는 제대로 정렬이 되지 않았던 것이다. 따라서 this.parent(index) !== undefined 라고 수정하니까 잘 돌아갔다. 이 부분은 bubbleDown에서 this.leftChild(index)와 this.rightChild(index) 부분에서도 마찬가지로 수정해주면 된다.

 

이 부분 때문에 삽질을 좀 하긴 했지만 덕분에 정말 많은 것을 배워갈 수 있었던 문제인 것 같다. 0을 false로 간주한다는 것은 알고는 있었으나 어느 부분에서 활용이 되는지 실제로 사용해본적이 없어서 모르고 있었는데 이 기회에 확실히 알아갈 수 있었던 좋은 실패의 경험이었다고 생각한다.

 

(힙정렬에 대한 설명은 전에 자료구조 게시판에 업데이트한 적이 있으니 필요한 분은 찾아보시면 됩니다.)