[실버] 최소 힙 (1927번)_JS

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

 

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

 

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

*성공답안: 최소힙으로 해야지, 안그럼 시간초과

내 성공답안:
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\\n").map(Number) ;
let n = input.shift() ;

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

  getParentIndex(i) {  //부모노드 인덱스 구하기
    return Math.floor((i - 1) / 2);
  }

  getLeftChildIndex(i) { //왼쪽 자식노드 인덱스 구하기
    return i * 2 + 1;
  }

  getRightChildIndex(i) { //오른쪽 자식노드 인덱스 구하기
    return i * 2 + 2;
  }

  swap(a, b) {   //노드 바꾸기
    const temp = this.heap[a];
    this.heap[a] = this.heap[b];
    this.heap[b] = temp;
  }

  push(data){
    this.heap.push(data) ;
    let currentIndex = this.heap.length-1 ;
    let parent = this.getParentIndex(currentIndex)
    while ((this.heap[parent])&&(this.heap[currentIndex] < this.heap[parent])){ //부모보다 현재 노드(추가노드)가 작을때 실행 - 최소힙이라
        this.swap(currentIndex, parent)
        currentIndex = parent ;
        parent = this.getParentIndex(currentIndex)
    }
  }

  shift(){
    if (this.heap.length == 0 ) return 0 ;

    let min = this.heap[0] ;
    this.heap[0] = this.heap[this.heap.length-1] ;
    this.heap.pop() ;
    let nowIndex = 0 ;
    

    while (this.heap[this.getLeftChildIndex(nowIndex)]){
      let minChild = this.getLeftChildIndex(nowIndex) ;

      if ((this.getRightChildIndex(nowIndex))&&(this.heap[minChild] > this.heap[this.getRightChildIndex(nowIndex)])){
        minChild  = this.getRightChildIndex(nowIndex)
      }

      if (this.heap[nowIndex] > this.heap[minChild]) this.swap(nowIndex,minChild) ;
      nowIndex = minChild ;
    }
    return min;
  }
}

let heap = new Heap() ;
let answer = ""
input.forEach(x => {
  if (x == 0 ) answer += `${heap.shift()}\\n` ;
  else heap.push(x) ;
})
console.log(answer.trim())

>> 최소힙: <https://algoroot.tistory.com/m/69> 참고
>> 하나 뽑을때 logN > n개 뽑으면 NlogN ;

 

---

실패답안

---

내 답안: 시간초과
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\\n").map(Number) ;
let n = input.shift() ;

function push(arr, num){ //arr.length !== 0
  if (arr.length == 0) {
    arr.push(num) ;
  } else {
    let pushIndex = findIndex(arr,num) ;
    for (let i = arr.length ; i > pushIndex ; i-- ){
      arr[i] = arr[i-1] ;
    }
    arr[pushIndex] = num ;
  }
}

function findIndex(arr, num){
  let a = 0 ; 
  let b = arr.length ;
  while (a <= b){
    let mid = Math.floor((a+b)/2) ;
    if (num > arr[mid]) b = mid-1 ;
    else if (num < arr[mid]) a = mid + 1 ;
    else return mid
  }
  return a ;
}

let arr = [] ;
let answer = ""
for (let i = 0 ; i < input.length ; i++ ){
  if (input[i] == 0 ) {
    answer += (arr.length == 0 )? "0\\n" : `${arr.pop()}\\n` ;
  } else push(arr, input[i]) ;
}
console.log(answer.trim()) ;

내 답안: 이것도 시간초과..
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\\n").map(Number) ;
let n = input.shift() ;

class Node{
  constructor(data){
    this.data = data ;
    this.right = null ;
    this.left = null ;
  }
}

class Tree{
  constructor(data){
    let init = new Node(data)
    this.root = init ;
    this.count = 1 ;
  }

  insert(data){
    let newNode = new Node(data) ;
    let nowNode = this.root ;
    while(nowNode){
      if (nowNode.data >= data){
        if (!nowNode.left){
          nowNode.left = newNode ;
          this.count++
          return ; 
        }
      nowNode = nowNode.left ;
      }
      if (nowNode.data < data){
        if (!nowNode.right){
          nowNode.right = newNode ;
          this.count++
          return ; 
        }
      nowNode = nowNode.right ;
      }
    }
  }

  return(){
    if (this.count == 1 ) return 0

    //left가 없는 맨 아래까지 내려가기
    let nowNode = this.root.right ;
    let upNode = this.root ;
    while(nowNode.left != null){
      upNode = nowNode ;
      nowNode = nowNode.left ;
    }
    let answer = nowNode.data ;

    //left 없는 경우/ right가 있는 경우 준비작업
    let val = [] ;
    let val_data = [] ;
    if (nowNode.right) {
      nowNode = nowNode.right ;
      val.push(nowNode) ;
      while (val.length !== 0 ){
        let valNode = val.pop() ;
        if (valNode.left) val.push(valNode.left) ;
        if (valNode.right) val.push(valNode.right) ;
        val_data.push(valNode.data) ;
      }
    }

    if (upNode.data == 0 ) upNode.right = null ;
    else upNode.left = null ;
    this.count-- ;

    if (val_data.length == 0 ) return answer ;
    else {
      val_data.forEach(x => {
        this.insert(x)
        this.count--
      }) ;
      return answer
    }
  }
}

let tree = new Tree(0)
let answer = "" ;
for (let i = 0 ; i < input.length ; i++ ){
  if (input[i] == 0 ) answer += `${tree.return()}\\n` ;
  else tree.insert(input[i]) ;
}
console.log(answer.trim())

>> 이진트리: 정렬된 값이 들어오면 트리가 한쪽으로 치우쳐서 시간이 오래걸림