출처: 프로그래머스 코딩테스트 이중 우선순위큐(Heap) 3번째 문제
(https://programmers.co.kr/learn/courses/30/lessons/42628)
문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어 수신 탑(높이)
---------------------------------------------
I 숫자 큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
제한사항
- operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
- operations의 원소는 큐가 수행할 연산을 나타냅니다.
- 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
풀이 방법
- 이중 우선 순위 큐를 대칭 최소채대 힙로 구현한다.
- 주어진 명령어들을 정제하여 배열로 만든다.
- 주어진 명령어의 동작을 process 변수에 담아 해당 명령을 실행할 수 있게 한다.
- I : 큐에 주어진 숫자를 삽입합니다.
- D 1 : 큐에서 최댓값을 삭제합니다.
- D -1 : 큐에서 최솟값을 삭제합니다.
- 명령어들의 배열을 하나씩 순회하면서 process를 실행한다.
- 모든 명령이 끝나면 최소값과 최대값을 반환한다.
소스 코드
function solution(operations) {
const newOpertaions = operations.map((el) => {
const [operation, data] = el.split(" ")
return { operation, data: +data }
})
const process = {
I: (DPQ, data) => DPQ.push(data),
D: (DPQ, data) => {
if (DPQ.size() < 1) {
return
} else if (DPQ.size() === 1) {
DPQ.queue.pop()
return
}
data === 1 ? DPQ.popMax() : DPQ.popMin()
},
}
const dualPriorityQueue = new SMMH()
for (const { operation, data } of newOpertaions) {
process[operation](dualPriorityQueue, data)
//console.log(operation, data)
//dualPriorityQueue.display()
}
if (dualPriorityQueue.size() === 0) {
return [0, 0]
} else if (dualPriorityQueue.size() === 1) {
const popData = dualPriorityQueue.queue.pop()
return [popData, popData]
}
const minData = dualPriorityQueue.queue[2]
const maxData = dualPriorityQueue.queue[3]
return [ maxData, minData ]
}
class SMMH {
constructor() {
this.queue = [null, null]
this.MIN_NODE_IDX = 2
this.MAX_NODE_IDX = 3
}
size() {
return this.queue.length - 2
}
push(data) {
const queue = this.queue
queue.push(data)
const currentIdx = queue.length - 1
if (currentIdx == this.MIN_NODE_IDX) {
return
}
const depth = this.getDepth(currentIdx)
const offset = Math.pow(2, depth) + Math.pow(2, depth - 1)
const flag = currentIdx < offset ? "left" : "right"
//console.log("depth: ", depth, " offset: ", offset, " flag: ", flag)
const result = this.process1(queue, depth, currentIdx, flag)
this.bubleUp(queue, result.flag, result.idx)
//console.log("pushData: ", data)
//this.display()
}
popMin() {
const queue = this.queue
const queueSize = queue.length
const popData = queue[this.MIN_NODE_IDX]
if (queueSize <= this.MAX_NODE_IDX + 1) {
this.swap(queue, this.MIN_NODE_IDX, this.MAX_NODE_IDX)
queue.pop()
return popData
}
const resultIdx = this.bubleDown(queue, "left")
if (queueSize === this.MAX_NODE_IDX + 2) {
queue.pop()
return popData
}
queue[resultIdx] = queue[queueSize - 1]
queue.pop()
const depth = this.getDepth(resultIdx)
this.process1(queue, depth, resultIdx, "left")
//this.display()
return popData
}
popMax() {
const queue = this.queue
const queueSize = queue.length
const popData = queue[this.MAX_NODE_IDX]
if (queue.length < this.MAX_NODE_IDX + 1) {
return queue.pop()
}
if (queueSize === this.MAX_NODE_IDX + 2) {
queue.pop()
return popData
}
const resultIdx = this.bubleDown(queue, "right")
//console.log("resultIdx: ", resultIdx)
queue[resultIdx] = queue[queueSize - 1]
queue.pop()
//this.display()
return popData
}
getDepth(idx) {
for (let n = 1048576, depth = 20; depth > 0; n = n >> 1, depth--) {
if ((n & idx) === n) {
return depth
}
}
}
insertData(queue, flag, depth, currentIdx) {
this.bubleUp(queue, flag, currentIdx)
}
pushToLeft(queue, depth, currentIdx) {
this.process1(queue, depth, currentIdx, "left")
this.bubleUp(queue, "left")
}
pushToRight(queue, depth, currentIdx) {
this.process1(queue, depth, currentIdx, "right")
this.bubleUp(queue, "right")
}
process1(queue, depth, currentIdx, flag) {
let siblingIdx = flag === "left" ? currentIdx + Math.pow(2, depth - 1) : currentIdx - Math.pow(2, depth - 1)
//console.log("siblingIdx: ", siblingIdx)
siblingIdx = !queue[siblingIdx] ? Math.trunc(siblingIdx / 2) : siblingIdx
const condition = {
left: (currentIdx, siblingIdx) => queue[currentIdx] < queue[siblingIdx],
right: (currentIdx, siblingIdx) => queue[currentIdx] > queue[siblingIdx],
}
if (!condition[flag](currentIdx, siblingIdx)) {
this.swap(queue, siblingIdx, currentIdx)
return { flag: flag === "left" ? "right" : "left", idx: siblingIdx }
}
return { flag, idx: currentIdx }
}
bubleUp(queue, flag, currentIdx) {
let parentIdx
const condition = {
left: (currentIdx, parentIdx) => queue[currentIdx] > queue[parentIdx],
right: (currentIdx, parentIdx) => queue[currentIdx] < queue[parentIdx],
}
while (currentIdx > this.MAX_NODE_IDX) {
parentIdx = Math.trunc(currentIdx / 2)
if (condition[flag](currentIdx, parentIdx)) {
break
}
this.swap(queue, currentIdx, parentIdx)
currentIdx = parentIdx
}
}
bubleDown(queue, flag) {
let currentIdx = flag === "left" ? this.MIN_NODE_IDX : this.MAX_NODE_IDX
const queueSize = this.queue.length
while (currentIdx < queueSize) {
const result = this.check(queue, currentIdx, flag)
//console.log("checkReulst:", result)
if (result === null) {
break
}
queue[currentIdx] = queue[result]
currentIdx = result
}
return currentIdx
}
check(queue, idx, flag) {
const leftChildIdx = idx * 2
const rightChildIdx = idx * 2 + 1
if (!queue[leftChildIdx]) {
return null
} else if (!queue[rightChildIdx]) {
return leftChildIdx
}
const condition = {
left: (leftChildIdx, rightChildIdx) => queue[leftChildIdx] < queue[rightChildIdx],
right: (leftChildIdx, rightChildIdx) => queue[leftChildIdx] > queue[rightChildIdx],
}
return condition[flag](leftChildIdx, rightChildIdx) ? leftChildIdx : rightChildIdx
}
swap(queue, i, j) {
;[queue[i], queue[j]] = [queue[j], queue[i]]
}
display() {
let depth
for (depth = 1; this.queue.length > Math.pow(2, depth); depth++) {
console.log(" depth: ", depth, " elements: ", this.queue.slice(Math.pow(2, depth), Math.pow(2, depth + 1)))
}
}
}후기
어떻게하면 최대값과 최소값을 한번에 큐에 저장시킬 수 있을까 고민하다가 구글링 도중 symmetric min max heap를 발견하여 이를 구현한 논문을 참고하여 해당 문제를 풀었다. 생각보다 까다로워서 힙을 구현하기가 어려워서 시간이 오래 걸린 문제였다.
