프로그래머스 JS [이중우선순위큐] 최대 힙, 최소 힙(Heap) 으로 풀고 싶다

이중우선순위큐 문제 보기

문제 설명

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

명령어수신 탑(높이)

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

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

---

원래 문제는 최대 힙(Max Heap)과 최소 힙(Min Heap)을 이용해 푸는 것 같으나...

< Heap이 뭔지 알아보러 가기 >

 

그림을 통해 쉽게 설명해주므로 원리는 이해가 가지만, 나에게 이를 javascript 코드로 구현하기는 쉽지 않다.

 

최대 힙 노드 삽입 정렬 과정

• 일차원 배열의 완전 이진 트리의 루트가 가장 큰 값이 된다.
• 자식 노드는 부모 노드보다 작은 값이다.

새로 삽입할 값을 배열의 마지막에 삽입한다. =>

마지막에 삽입한 값과 부모 노드(floor.( N / 2 )-1)의 값을 비교한다. =>

크기가 크다면 부모 노드와 자리를 바꾸는 과정을 최상단 노드까지 반복한다.

 

최대 힙 노드 삭제 정렬 과정

• 최대 힙에서 삭제할 값은 항상 가장 큰 값인 루트 노드가 된다.
• 루트 노드의 빈 자리에 마지막 노드를 채운다.

자식 노드와(N*2-1)와 대소 비교를 통해 정렬을 한다.

 

여기까지는 할 만 하지만, 여기서 문제는 최대 힙 노드와 최소 힙 노드가 같이 있다는 것.

최대 힙 노드에 삽입 정렬

최소 힙 노드에 삽입 정렬

 

최댓값 삭제

최대 힙 노드 삭제 정렬 =>

최소 힙 노드에서 삭제한 값과 같은 값 제거 <<< 이 방법을 O(logN)으로 구현하는 방법을 못 떠올리겠다.

(최솟값 삭제는 반대로 똑같은 방식)

---

테스트 케이스는 실제로 시간초과를 낼 만큼 길지 않아서 sort() 정렬을 이용해 O(N)으로 풀었다.

Heap을 쓰지 않고 풀면 어렵지 않은 단순한 정렬 문제이다.

function solution(operations) {

  const numberArray = [];

  for (operation of operations) {

    const operationSplit = operation.split(" ");

    const command = operationSplit[0];

    const number = Number(operationSplit[1]);

// 명령이 I(삽입) 일 때는 삽입

    if (command === "I") {

      numberArray.push(number);

      continue;

    }

// 배열의 길이가 0 일 때는 최댓값, 최솟값 제거 명령 수행하지 않음

    if (numberArray.length === 0) {

      continue;

 

// 최댓값 오름차순 정렬 뒤 pop 

    } else if (number === 1) {

      numberArray.sort((a, b) => a - b);

      numberArray.pop();

// 최솟값: 내림차순 정렬 뒤 pop

    } else {

      numberArray.sort((a, b) => b - a);

      numberArray.pop();

    }

  }

// 내림차순 정렬한 뒤 최댓값과 최솟값을 반환, 조건에 따라 빈 배열인 경우 [0, 0] 반환

  numberArray.sort((a, b) => b - a);

  return numberArray.length ? [numberArray[0], numberArray.at(-1)] : [0, 0];

}

solution(["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]);