이중 우선순위 큐
이 문제를 풀어보자
https://www.acmicpc.net/problem/7662
처음에 나는 이 문제를 풀지 못했다.
문제를 풀지 못한 이유는
- 최대힙과 최소힙을 둘 다 사용하는 것으로 이중 우선순위 큐를 구현했을 때, 한 큐에서 삭제한 값을 다른 큐에서는 어떻게 지워야 할 지 잘 생각이 나지 않아서
- 첫 번째 구현에서 메모리초과가 발생하여
이다.
내 초기 접근을 복기해보고, 성공한 문제풀이로 다가갈 수 있었던 깨달음 포인트를 살펴보자.
[문제풀이 기초 알고리즘 숙지] 우선순위 큐(최대힙, 최소힙)구현
아래 코드는 내가 힙큐 알고리즘 문제를 풀 때 사용하는 최대힙 구현 코드이다. 배열로 우선순위 큐를 구현했다.
최대힙의 매서드 compare 내부의 등호방향만 바꿔주면 최소힙이 된다.
최대힙과 최소힙을 이용해서 이중 우선순위 큐를 구현해 볼 예정이기에, 한 번 소개하고 간다.
class MaxHeap {
constructor() {
this.heap = []
}
compare(a, b) {
return this.heap[a] < this.heap[b]
}
push(n) {
this.heap.push(n)
let childIdx = this.heap.length - 1
while (Math.floor((childIdx - 1) / 2) >= 0) {
const parentIdx = Math.floor((childIdx - 1) / 2)
if (this.compare(childIdx, parentIdx)) break
[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
childIdx = parentIdx
}
}
pop() {
if (this.heap.length === 0) return
else if (this.heap.length === 1) {
const popped = this.heap[0]
this.heap.pop()
return popped
} else {
const popped = this.heap[0]
this.heap[0] = this.heap[this.heap.length - 1]
this.heap.pop()
let parentIdx = 0
while (parentIdx * 2 + 1 < this.heap.length) {
let childIdx = parentIdx * 2 + 1
childIdx + 1 < this.heap.length &&
this.heap[childIdx] < this.heap[childIdx + 1] &&
childIdx++
if (this.compare(childIdx, parentIdx)) break
[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
parentIdx = childIdx
}
return popped
}
}
isEmpty() {
return this.heap.length === 0
}
}이중 우선순위 큐
개념부터 체크
실패한 1차 구현 with JS
이중 우선순위 큐를 최대힙과 최소힙을 함께 관리하는 dual structure 방식으로 구현해보려 시도했다.
각각의 힙큐에서 최대값, 최소값을 뽑는 작업은 간단하지만, 큐에서 삭제된 값을 다른 큐에 반영해야 하는 작업을 어떻게 해야 할 지 고민을 했는데, 이번 시도에서는 remove(value)매서드에서 slice를 통해 value값을 제외 한 새로운 배열을 this.heap에 재할당하는 방법을 시도했다.
코드는 아래와 같고, 테스트 케이스는 통과하지만, 메모리 초과가 발생했다.
const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
})
class MaxHeap {
constructor() {
this.heap = []
}
compare(a, b) {
return this.heap[a] < this.heap[b]
}
push(n) {
this.heap.push(n)
let childIdx = this.heap.length - 1
while (Math.floor((childIdx - 1) / 2) >= 0) {
const parentIdx = Math.floor((childIdx - 1) / 2)
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
childIdx = parentIdx
}
}
pop() {
if (this.heap.length === 0) return
else if (this.heap.length === 1) {
const popped = this.heap[0]
this.heap.pop()
return popped
} else {
const popped = this.heap[0]
this.heap[0] = this.heap[this.heap.length - 1]
this.heap.pop()
let parentIdx = 0
while (parentIdx * 2 + 1 < this.heap.length) {
let childIdx = parentIdx * 2 + 1
childIdx + 1 < this.heap.length && this.compare(childIdx, childIdx + 1) && childIdx++
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
parentIdx = childIdx
}
return popped
}
}
isEmpty() {
return this.heap.length === 0
}
remove(value) {
const idx = this.heap.findIndex((el) => el === value)
this.heap = this.heap.slice(0, idx).concat(this.heap.slice(idx + 1))
}
}
class MinHeap {
constructor() {
this.heap = []
}
compare(a, b) {
return this.heap[a] > this.heap[b]
}
push(n) {
this.heap.push(n)
let childIdx = this.heap.length - 1
while (Math.floor((childIdx - 1) / 2) >= 0) {
const parentIdx = Math.floor((childIdx - 1) / 2)
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
childIdx = parentIdx
}
}
pop() {
if (this.heap.length === 0) return
else if (this.heap.length === 1) {
const popped = this.heap[0]
this.heap.pop()
return popped
} else {
const popped = this.heap[0]
this.heap[0] = this.heap[this.heap.length - 1]
this.heap.pop()
let parentIdx = 0
while (parentIdx * 2 + 1 < this.heap.length) {
let childIdx = parentIdx * 2 + 1
childIdx + 1 < this.heap.length && this.compare(childIdx, childIdx + 1) && childIdx++
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
parentIdx = childIdx
}
return popped
}
}
isEmpty() {
return this.heap.length === 0
}
remove(value) {
const idx = this.heap.findIndex((el) => el === value)
this.heap = this.heap.slice(0, idx).concat(this.heap.slice(idx + 1))
}
}
const answer = []
let i = 0
let lines = 0
let lineCounter = 0
let maxHeap = new MaxHeap()
let minHeap = new MinHeap()
rl.on('line', (l) => {
if (i++ === 0) return
if (l.length === 1) {
lines = +l
return
}
const [cmd, value] = l.split(' ')
if (cmd === 'I') {
maxHeap.push(+value)
minHeap.push(+value)
} else if (cmd === 'D' && value === '1') {
const popped = maxHeap.pop()
if (popped) {
minHeap.remove(popped)
}
} else {
const popped = minHeap.pop()
if (popped) {
maxHeap.remove(popped)
}
}
if (lines === ++lineCounter) {
if (maxHeap.isEmpty()) {
answer.push('EMPTY')
} else {
const max = maxHeap.pop()
const min = minHeap.pop()
answer.push([max, min])
}
lines = 0
lineCounter = 0
}
}).on('close', () => {
console.log(answer)
})
위 코드의 문제점과 개선안
- 같은 코드가 많이 반복되는 클래스가 존재한다.
MinHeap과 MaxHeap은 compare함수만 다르지, 내부 구현은 동일하다. 불필요하게 코드가 비대해졌다.
=> 그래서 compare함수를 객체 생성시에 생성자함수를 통해 외부에서 주입해주는 방식으로 개선했다.
class Heap {
constructor(compareFunc) {
this.heap = []
this.compareFunc = compareFunc
}
compare(a, b) {
return this.compareFunc(this.heap[a], this.heap[b])
}
push(n) {
this.heap.push(n)
let childIdx = this.heap.length - 1
while (Math.floor((childIdx - 1) / 2) >= 0) {
const parentIdx = Math.floor((childIdx - 1) / 2)
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
childIdx = parentIdx
}
}
pop() {
if (this.heap.length === 0) return
else if (this.heap.length === 1) {
const popped = this.heap[0]
this.heap.pop()
return popped
} else {
const popped = this.heap[0]
this.heap[0] = this.heap[this.heap.length - 1]
this.heap.pop()
let parentIdx = 0
while (parentIdx * 2 + 1 < this.heap.length) {
let childIdx = parentIdx * 2 + 1
childIdx + 1 < this.heap.length && this.compare(childIdx, childIdx + 1) && childIdx++
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
parentIdx = childIdx
}
return popped
}
}
isEmpty() {
return this.heap.length === 0
}
remove(value) {
const idx = this.heap.findIndex((el) => el === value)
this.heap = this.heap.slice(0, idx).concat(this.heap.slice(idx + 1))
}
}이 클래스 하나로 우리는 MinHeap과 MaxHeap을 생성할 수 있게 되었다.
const maxHeap = new Heap((a, b) => a < b)
const minHeap = new Heap((a, b) => a > b)
- 256 MB의 메모리제한을 고려하지 않은 input받기
Number 원시값은 8바이트의 크기를 갖는다. 문제에서 각 케이스는 최대 1,000,000개의 명령을 받을 수 있다고 했으니, 힙의 크기는 최대 8,000,000Byte = 8MByte가 될 것이다. 최소힙도 함께 관리하니 그 두 배인16MByte의 데이터를 관리하게 된다. 한 테스트의 힙 크기로만!
=> 그래서 input을 받을 때, fs가 아닌 readline 모듈을 사용하는 것이 더 바람직하다고 판단했다.
remove(value)매서드에서 사용한Array.prototype.slice()
slice의 시간 복잡도는 O(N)이다. 백만 개의 요소 중, 하나를 지우는 작업의 대가로 조금 과하다는 생각을 했다.
remove를 slice로 구현한 것은 최대힙과 최소힙 간 요소들의일 대 일 대응을 구현하기 위해서였다.
최대힙에서 지운 값이 최소힙에서도 지워지도록, 그 반대로도 말이다. 그런데 이 부분에서 비효율이 나는 듯 했다. 심지어, slice를 통해서 새로운 배열을 생성하니, 메모리도 추가로 사용하는 셈이라, 공간복잡도도 높아지는 구현이라 생각했다.
=> 그래서 remove할 때도 pop을 할 때처럼 remove하는 요소의 위치에다가 힙의 맨 끝 값을 옮겨온 다음, 큐를 재정렬하는 로직을 도입했다. 큐 재정렬은 logN의 시간복잡도이니, 훨씬 빨라졌을 것이라 장담한다. 그리고 slice를 사용하여 구현할 때보다 메모리도 훨씬 덜 사용한다!
실패한 2차 구현 with JS
위 개선사항들을 반영하여 구현한 2차 풀이 코드이다. 하지만 결과는 시간초과 였다. 메모리초과는 일단 통과했으나, 시간 복잡도에서 걸렸다.
class Heap {
constructor(compareFunc) {
this.heap = []
this.compareFunc = compareFunc
}
compare(a, b) {
return this.compareFunc(this.heap[a], this.heap[b])
}
push(n) {
this.heap.push(n)
let childIdx = this.heap.length - 1
while (Math.floor((childIdx - 1) / 2) >= 0) {
const parentIdx = Math.floor((childIdx - 1) / 2)
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
childIdx = parentIdx
}
}
pop() {
if (this.heap.length === 0) return
else if (this.heap.length === 1) {
const popped = this.heap[0]
this.heap.pop()
return popped
} else {
const popped = this.heap[0]
this.heap[0] = this.heap[this.heap.length - 1]
this.heap.pop()
let parentIdx = 0
while (parentIdx * 2 + 1 < this.heap.length) {
let childIdx = parentIdx * 2 + 1
childIdx + 1 < this.heap.length && this.compare(childIdx, childIdx + 1) && childIdx++
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
parentIdx = childIdx
}
return popped
}
}
isEmpty() {
return this.heap.length === 0
}
remove(value) {
let parentIdx = this.heap.findIndex((el) => el === value)
this.heap[parentIdx] = this.heap[this.heap.length - 1]
this.heap.pop()
while (parentIdx * 2 + 1 < this.heap.length) {
let childIdx = parentIdx * 2 + 1
childIdx + 1 < this.heap.length && this.compare(childIdx, childIdx + 1) && childIdx++
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
parentIdx = childIdx
}
}
reset() {
this.heap = []
}
}
const readline = require('readline')
const fs = require('fs')
const rl = readline.createInterface({
input: process.platform === 'linux' ? process.stdin : fs.createReadStream('test/test.txt'),
output: process.stdout,
terminal: false,
})
const answer = []
const maxHeap = new Heap((a, b) => a < b)
const minHeap = new Heap((a, b) => a > b)
let index = 0
let endLine = 0
rl.on('line', (line) => {
if (index === 0) {
index++
return
}
if (index > endLine) {
endLine = +line + index++
minHeap.reset()
maxHeap.reset()
return
}
const [cmd, value] = line.split(' ')
if (cmd === 'I') {
maxHeap.push(+value)
minHeap.push(+value)
} else {
if (value === '1') {
const popped = maxHeap.pop()
if (popped) {
minHeap.remove(popped)
}
} else {
const popped = minHeap.pop()
if (popped) {
maxHeap.remove(popped)
}
}
}
if (index === endLine) {
maxHeap.isEmpty()
? answer.push('EMPTY')
: answer.push([maxHeap.heap[0], minHeap.heap[0]].join(' '))
}
index++
})
rl.on('close', () => {
console.log(answer.join('\n'))
})
시간 복잡도에서 걸린 이유 추리
이중 우선순위 큐에서는, 최대힙에서 삭제한 값을 최소힙에서도 삭제해주어야하고, 최소힙에서 삭제한 값을 최대힙에서 삭제해주어야 한다.
내 코드에서 이 작업을 하는 메소드는 remove였다.그런데 remove가 매우 비효율적으로 동작하는 듯하다. 어떻게 이 작업을 최적화할 수 있을까?
문제풀이 성공한 3차 구현
반례를 통한 로직의 허점 찾기
위 코드가 동작하지 않는 근본적인 이유를 한 반례를 통해 깨달았다. 내게 깨달음을 주었던 반례는 아래와 같다.
반례
1
9
I 36
I 37
I 38
D 1
D 1
I 39
I 40
D -1
D -1
//정답: 40 40
//코드 출력값: 40 39이 반례에서 깨달았던 것은 A힙에서 값을 제거하고 나면, 다음에 root로 올라오는 수가 유효한 수인지는 보장할 수 없다는 것이었다. 이를 방지하기 위해서는 유효한 수가 root로 올라올 때까지 힙에서 pop을 계속해주어야 한다.
위 예시로 보면, 36 37 38이 push된 상태에서 두 번 최대값을 pop하게 되면 최대힙에는 36만 남게된다. 이 때 최소힙에서는 36 37 38이 그대로 저장되어 있는 상태이다.(36이라는 수는 아직 pop되지 않은 유효한 수이기에 최소힙에서 pop을 할 수 없다). 이 상태에서 39, 40을 추가하게 되면 최대힙은 36 39 40으로, 최소힙은 36 37 38 39 40이 되게 된다.
이제 최소힙에서 pop을 두 번하는 경우를 생각해보자. root의 36은 유효한 값이기에, 36이 pop된다. 다음 root로 들어오는 수는 37인데, 37은 이미 pop된 수이다. 이미 다른 힙에서 pop되었던 수는 유효하지 않다. 따라서 그대로 pop해서 버린다. 이후 38도 마찬가지로 pop해서 버린다. 그래서 그 다음 수인 39가 다음 유효한수로서 유의미하게 pop이 되고, 최소힙에는 40이라는 수만 남게된다.
유효한 수와 유효하지 않은 수를 map으로 관리하기
이제 내가 해야 할 다음 단계는 수의 유효성을 코드 어디에선가 관리하는 것이다.
n이라는 숫자의 등장횟수를 관리하여 push될 때는 +1을 하고, pop될 때는 -1을 한다면 root에서 n이라는 숫자를 만났을 때 이 수가 유효한지 여부를 바로 판단할 수 있을 것이다.
그래서 나는 Map 객체를 사용하여 이 값을 관리했다.
그리고 문제풀이에 성공했다.
아래는 성공한 풀이 코드이다. Heap 두개와 Map객체 하나를 가지고 이중우선순위큐 클래스를 구현하여 사용했다. 세부 구현을 클래스 내부로 가져와서 핵심 코드는 가독성이 조금 높아졌다.
class Heap {
constructor(compareFunc) {
this.heap = []
this.compareFunc = compareFunc
}
compare(a, b) {
return this.compareFunc(this.heap[a], this.heap[b])
}
push(n) {
this.heap.push(n)
let childIdx = this.heap.length - 1
while (Math.floor((childIdx - 1) / 2) >= 0) {
const parentIdx = Math.floor((childIdx - 1) / 2)
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
childIdx = parentIdx
}
}
pop() {
if (this.heap.length === 0) return null
else if (this.heap.length === 1) {
const popped = this.heap[0]
this.heap.pop()
return popped
} else {
const popped = this.heap[0]
this.heap[0] = this.heap[this.heap.length - 1]
this.heap.pop()
let parentIdx = 0
while (parentIdx * 2 + 1 < this.heap.length) {
let childIdx = parentIdx * 2 + 1
childIdx + 1 < this.heap.length && this.compare(childIdx, childIdx + 1) && childIdx++
if (this.compare(childIdx, parentIdx)) break
;[this.heap[parentIdx], this.heap[childIdx]] = [this.heap[childIdx], this.heap[parentIdx]]
parentIdx = childIdx
}
return popped
}
}
isEmpty() {
return this.heap.length === 0
}
reset() {
this.heap = []
}
top() {
return this.heap[0]
}
}
class DoubleEndedPQueue {
constructor() {
this.maxHeap = new Heap((a, b) => a < b)
this.minHeap = new Heap((a, b) => a > b)
this.map = new Map()
}
push(value) {
this.maxHeap.push(value)
this.minHeap.push(value)
const previous = this.map.get(value)
previous ? this.map.set(value, previous + 1) : this.map.set(value, 1)
}
popMax() {
const popped = this.maxHeap.pop()
if (popped !== null) {
const previous = this.map.get(popped)
this.map.set(popped, previous - 1)
this.clear()
}
}
popMin() {
const popped = this.minHeap.pop()
if (popped !== null) {
const previous = this.map.get(popped)
this.map.set(popped, previous - 1)
this.clear()
}
}
topMax() {
return this.maxHeap.top()
}
topMin() {
return this.minHeap.top()
}
clear() {
while (!this.minHeap.isEmpty() && !(this.map.get(this.minHeap.top()) > 0)) {
this.minHeap.pop()
}
while (!this.maxHeap.isEmpty() && !(this.map.get(this.maxHeap.top()) > 0)) {
this.maxHeap.pop()
}
}
reset() {
this.maxHeap.reset()
this.minHeap.reset()
this.map.clear()
}
}
const readline = require('readline')
const fs = require('fs')
const rl = readline.createInterface({
input: process.platform === 'linux' ? process.stdin : fs.createReadStream('test/test.txt'),
output: process.stdout,
terminal: false,
})
const answer = []
const depq = new DoubleEndedPQueue()
let index = 0
let endLine = 0
rl.on('line', (line) => {
if (index === 0) {
index++
return
}
if (index > endLine) {
endLine = +line + index++
depq.reset()
return
}
let [cmd, value] = line.split(' ')
value = Number(value)
if (cmd === 'I') {
depq.push(value)
} else {
if (value === 1) {
depq.popMax()
} else {
depq.popMin()
}
}
if (index === endLine) {
depq.clear()
depq.maxHeap.isEmpty() || depq.minHeap.isEmpty()
? answer.push('EMPTY')
: answer.push([depq.topMax(), depq.topMin()].join(' '))
}
index++
})
rl.on('close', () => {
console.log(answer.join('\n'))
})교훈
한 문제를 오래 붙잡고 있는 것은 얼핏 비효율적이다. 특히나 정량적인 시험을 공부할 때는 더욱 그렇게 보인다. 하지만, 그 시간을 나는 투자라고 생각한다. 충분히 고민하고, 시도하면서 깨달음을 얻는 과정이 진정한 성장이라 생각한다. 이 문제를 풀어내고 너무 뿌듯해서 잘난 듯이 또 몇 자 적어보았다 히히.
안녕하세요 개발자 윤승록입니다. 내 성장을 가시적으로 기록하기 위해 블로그를 운영중입니다.