[프로그래머스/Javascript/Heap] 이중우선순위큐

1. 서론

 위 문제는 Heap으로 분류되어 있으나, javascript 에서는 Heap에 대한 라이브러리가 존재하지 않기때문에 직접 구현해야한다. heap에 대한 코드는 이전에 작성한 jun0127.tistory.com/11 에 있는 코드를 그대로 사용하였다.

 

2. 문제설명(출처: programmers.co.kr/learn/courses/30/lessons/42628)

3. 문제 풀이

 1) operations의 명령어에 따라 I가 나오면 우선순위 큐에 해당 데이터 값을 enqueue한다.

 2) 사전에 구현된 heap 코드는 min heap이기 때문에 D 1 명령어가 나오면 min heap을 max heap으로 변경하고 다시 min heap상태로 되돌린다.

 3) D -1 명령어가 나오면 heap이 항상 min heap 유지하기 때문에 일반적인 remove 연산을 한다.

 4) 마지막으로 min heap일 때, root 값을 구해 최솟값을 얻고, max heap으로 변경한 뒤 root 값을 구해 최댓값을 획득한다.

 

4. 결과코드

function solution(operations) {
  var answer = [];
  var h = new Heap();
  for(let operation of operations){
    let oper = operation.split(' ')
    if(oper[0] == 'I'){
      h.insert(Number(oper[1]), Number(oper[1]))
    }else{
      if(oper[1] == '-1'){
        h.remove()
      }else{
        h.convertMaxHeap()
        h.remove()
        h.convertMinHeap()
      }
    }
  }
  
  if(!h.isEmpty()){
    h.convertMaxHeap()
    answer.push(h.peek().value)
    h.convertMinHeap()
    answer.push(h.peek().value)
  }else{
    answer = [0, 0]
  }
  return answer;
}