[Algorithm] 이중우선순위 큐

📋 문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어수신 탑(높이)

I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

제한 사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

입출력 예

["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

 

 

✏️ 풀이

배열(operations)의 길이가 1,000,000 이하이기 때문에 당연히 매번 정렬을 시켜주는 것은 효율성 측면에서 통과되지 않을 것이라고 생각했다. 이후 힙을 사용해서 하는 방법을 시도하려고 고민했는데 최소값, 최대값 두 가지를 고려해야 했기 때문에 max heap과 min heap을 둘 다 사용해야겠다고 생각하고 문제를 풀기 시작했다.

 

"I" 명령어가 입력되면 두 가지 힙에 값을 넣어준다. "D" 명령어가 입력되면 최대값을 빼는 1의 경우 max heap에서 최대값을 빼주고 반대인 경우에는 min heap에서 최소값을 빼줬다. 추가적으로 cnt라는 변수를 통해서 현재 큐에 있는 숫자 개수를 카운팅 해줬는데 넣어줄 때는 둘다 넣어주지만 뺄때는 각각의 힙에서 빼기 때문에 갯수 차이가 나기 때문이다. for문을 돌고 answer를 반환하기 전에 answer에 각각 힙에서 뺀 값을 넣어주는데 이때 의도치 않은 값이 나올 수 있다. 만약 heap에 "I"명령어가 10번, "D 1" 명령어가 10번 이루어지면 큐에는 값이 없어 [0, 0]을 반환해야 하는데 min heap에는 값이 남아있기 때문에 다른 값을 반환하게 된다. 따라서 cnt가 0이 되는 경우에 각 heap을 비워주기 위함이다.

 

 

⌨️ 코드

class MinHeap {
  constructor() {
    this.heap = [];
    this.heap.push(-1e9);
  }

  insert(value) {
    this.heap.push(value);
    this.upheap(this.heap.length - 1);
  }

  upheap(pos) {
    let temp = this.heap[pos];

    while (temp < this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }
    this.heap[pos] = temp;
  }

  get() {
    if (this.size() === 0) return 0;
    if (this.size() === 1) return this.heap.pop();
    const result = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1);
    return result;
  }

  downheap(pos, len) {
    let temp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child] > this.heap[child + 1]) child++;
      if (temp <= this.heap[child]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = temp;
  }

  clear() {
    this.heap = [-1e9];
  }

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

class MaxHeap {
  constructor() {
    this.heap = [];
    this.heap.push(1e9);
  }

  insert(value) {
    this.heap.push(value);
    this.upheap(this.heap.length - 1);
  }

  upheap(pos) {
    let temp = this.heap[pos];

    while (temp > this.heap[parseInt(pos / 2)]) {
      this.heap[pos] = this.heap[parseInt(pos / 2)];
      pos = parseInt(pos / 2);
    }
    this.heap[pos] = temp;
  }

  get() {
    if (this.size() === 0) return 0;
    if (this.size() === 1) return this.heap.pop();
    const result = this.heap[1];
    this.heap[1] = this.heap.pop();
    this.downheap(1, this.heap.length - 1);
    return result;
  }

  downheap(pos, len) {
    let temp = this.heap[pos],
      child;
    while (pos <= parseInt(len / 2)) {
      child = pos * 2;
      if (child < len && this.heap[child] < this.heap[child + 1]) child++;
      if (temp >= this.heap[child]) break;
      this.heap[pos] = this.heap[child];
      pos = child;
    }
    this.heap[pos] = temp;
  }

  clear() {
    this.heap = [1e9];
  }

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

function solution(operations) {
  var answer = [];
  let cnt = 0;

  const maxHeap = new MaxHeap();
  const minHeap = new MinHeap();

  for (const o of operations) {
    const [cmd, n] = o.split(' ');

    if (cmd === 'I') {
      maxHeap.insert(+n);
      minHeap.insert(+n);
      cnt += 1;
    } else {
      if (cnt) {
        if (n === '1') maxHeap.get();
        else minHeap.get();
        cnt -= 1;
      }
      if (!cnt) {
        minHeap.clear();
        maxHeap.clear();
      }
    }
  }

  answer.push(maxHeap.get());
  answer.push(minHeap.get());

  return answer;
}