[Programmers] 이중우선순위큐 문제 - (javascript)

문제 이름 :  이중우선순위큐 

---

 

<<< 문제 내용 >>>

---

 

function solution(operations) {
  let minHeap = [null];
  let maxHeap = [null];

  const swap = (m, a, b) => {
    if (m === "min") {
      [minHeap[a], minHeap[b]] = [minHeap[b], minHeap[a]];
      return;
    }

    [maxHeap[a], maxHeap[b]] = [maxHeap[b], maxHeap[a]];
  };

  const minHeapPush = (value) => {
    minHeap.push(value);
    let curIdx = minHeap.length - 1;
    let parIdx = (curIdx / 2) >> 0;

    while (curIdx > 1 && minHeap[curIdx] < minHeap[parIdx]) {
      swap("min", curIdx, parIdx);

      curIdx = parIdx;
      parIdx = (curIdx / 2) >> 0;
    }
  };

  const maxHeapPush = (value) => {
    maxHeap.push(value);
    let curIdx = maxHeap.length - 1;
    let parIdx = (curIdx / 2) >> 0;

    while (curIdx > 1 && maxHeap[curIdx] > maxHeap[parIdx]) {
      swap("max", curIdx, parIdx);

      curIdx = parIdx;
      parIdx = (curIdx / 2) >> 0;
    }
  };

  const minPop = () => {
    let min = minHeap[1];
    if (minHeap.length <= 2) minHeap = [null];
    else minHeap[1] = minHeap.pop();

    let curIdx = 1;
    let leftIdx = 2;
    let rightIdx = 3;

    if (!minHeap[leftIdx]) return min;

    if (!minHeap[rightIdx]) {
      if (minHeap[leftIdx] < minHeap[curIdx]) swap("min", leftIdx, curIdx);
      return min;
    }

    while (
      minHeap[curIdx] > minHeap[leftIdx] ||
      minHeap[curIdx] > minHeap[rightIdx]
    ) {
      const minIdx = minHeap[leftIdx] > minHeap[rightIdx] ? rightIdx : leftIdx;

      swap("min", minIdx, curIdx);

      curIdx = minIdx;
      leftIdx = curIdx * 2;
      rightIdx = curIdx * 2 + 1;
    }

    return min;
  };

  const maxPop = () => {
    let min = maxHeap[1];
    if (maxHeap.length <= 2) maxHeap = [null];
    else maxHeap[1] = maxHeap.pop();

    let curIdx = 1;
    let leftIdx = 2;
    let rightIdx = 3;

    if (!maxHeap[leftIdx]) return min;

    if (!maxHeap[rightIdx]) {
      if (maxHeap[leftIdx] > maxHeap[curIdx]) swap("max", leftIdx, curIdx);
      return min;
    }

    while (
      maxHeap[curIdx] < maxHeap[leftIdx] ||
      maxHeap[curIdx] < maxHeap[rightIdx]
    ) {
      const minIdx = maxHeap[leftIdx] < maxHeap[rightIdx] ? rightIdx : leftIdx;

      swap("max", minIdx, curIdx);

      curIdx = minIdx;
      leftIdx = curIdx * 2;
      rightIdx = curIdx * 2 + 1;
    }

    return min;
  };

  for (const data of operations) {
    const [oper, num] = data.split(" ");

    switch (oper) {
      case "I":
        minHeapPush(Number(num));
        maxHeapPush(Number(num));
        break;
      case "D":
        if (num === "1") {
          maxPop();
          if (minHeap.length === 1) break;
          minHeap.pop();
        } else {
          minPop();
          if (maxHeap.length === 1) break;
          maxHeap.pop();
        }
        break;
    }
  }

  return minHeap.length <= 1 ? [0, 0] : [maxHeap[1], minHeap[1]];
}

* 최소힙과 최대힙을 이용해 문제를 해결했다. 테스트 케이스가 굉장히 부실해서 그냥 queue를 이용해서 shift, pop만으로도 해결가능하다고 한다. 지금 위 코드도 테스트케이스가 부실해서 가능할 수도 있는 코드다.

 그 이유는 이중 우선순위 큐로 maxheap을 뽑을 때, minheap도 최대값을 빼야 하는데, minheap.pop()으로는 최대값을 뺀다고 보장할 수 없기 때문이다.

 이를 정확하게 해결하기 위해서는 백준의 중간 값을 구하는 문제와 유사하게 하여야 한다.

최대힙 (중간값) 최소힙으로 나누어서 최대힙과 최소힙의 개수차이를 1개이하로 유지하면서 중간값을 계속 갱신하고, 뽑을 땐 중간값을 뽑고 각각의 힙을 재 정리해서 중간값을 다시 산출하도록 하면 된다.

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.