이중 우선순위 큐
📚 문제 설명
이중 우선순위 큐는 기본적으로 우선순위 큐와 똑같다.
하지만 이중 우선순위 큐는 삭제시 최댓값 또는 최솟값을 정해서 삭제를 할 수 있다는 점이 다르다.
이중 우선순위 큐를 이용하여 삽입 또는 삭제 명령이 들어왔을 때, 모든 명령을 완료한 후에
큐에 남아있는 값 중에 최댓값과 최솟값을 출력하라.
단, 최댓값 최솟값을 공백으로 구분하고 큐가 비어있을 경우 "EMPTY" 출력.
👨🏻💻 풀이 과정
이 문제를 보고 가장 처음 생각했던 풀이는
- 2개의 우선순위 큐.
- 1개의 visited (
MAP) 변수.
우선순위 큐 구현에 관한 설명은 이번 포스트를 참고
위의 2 종류의 변수를 이용하여 푸는 방법이었다.
전체 풀이 순서는 아래와 같이 구성했다.
- 삽입 명령
- 최소힙, 최대힙 양쪽 모두 삽입
visited배열에 체크
- 삭제 명령
- 최대힙 혹은 최소힙에서 Pop.
visited배열에 체크
- 결과 출력
- 최대힙, 최소힙 최상단 확인.
visited배열 확인.- 이미 삭제한 값이 아닐 때까지 힙에서 제거.
- 결과 출력.
💡1차 제출 코드 (fail)
1차 제출 코드는 결론부터 말하면 실패했다.
전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const TestCase = parseInt(input.shift());
// 최소힙
class MinHeap {
constructor() {
this.heap = [null];
}
Insert(item) {
let Current = this.heap.length;
while (Current > 1) {
const Parent = Math.floor(Current / 2);
if (this.heap[Parent] > item) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else break;
}
this.heap[Current] = item;
}
Pop() {
if (this.heap.length > 2) {
const PopItem = this.heap[1];
this.heap[1] = this.heap.pop();
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
while (this.heap[LeftChild]) {
let Compare = LeftChild;
if (this.heap[RightChild] && this.heap[LeftChild] > this.heap[RightChild]) {
Compare = RightChild;
}
if (this.heap[Current] > this.heap[Compare]) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
} else break;
}
return PopItem;
} else if (this.heap.length === 2) {
return this.heap.pop();
} else {
return null;
}
}
GetLength() {
return this.heap.length - 1;
}
GetMin() {
return this.heap.length > 1 ? this.heap[1] : null;
}
}
// 최대힙
class MaxHeap {
constructor() {
this.heap = [null];
}
Insert(item) {
let Current = this.heap.length;
while (Current > 1) {
const Parent = Math.floor(Current / 2);
if (this.heap[Parent] < item) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else break;
}
this.heap[Current] = item;
}
Pop() {
if (this.heap.length > 2) {
const PopItem = this.heap[1];
this.heap[1] = this.heap.pop();
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
while (this.heap[LeftChild]) {
let Compare = LeftChild;
if (this.heap[RightChild] && this.heap[LeftChild] < this.heap[RightChild]) {
Compare = RightChild;
}
if (this.heap[Current] < this.heap[Compare]) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
} else break;
}
return PopItem;
} else if (this.heap.length === 2) {
return this.heap.pop();
} else {
return null;
}
}
GetLength() {
return this.heap.length - 1;
}
GetMax() {
return this.heap.length > 1 ? this.heap[1] : null;
}
}
// 각 테스트 실행함수.
const TestStart = () => {
const OrderCount = parseInt(input.shift());
const Orders = input.splice(0, OrderCount).map(v => v.split(' '));
const MinPQ = new MinHeap();
const MaxPQ = new MaxHeap();
let visited = new Map();
for (const [Order, Num] of Orders) {
if (Order === 'I') {
const InsertItem = parseInt(Num);
MinPQ.Insert(InsertItem);
MaxPQ.Insert(InsertItem);
if (visited.has(InsertItem)) {
visited.set(InsertItem, visited.get(InsertItem) + 1);
} else {
visited.set(InsertItem, 1);
}
} else {
if (Num === '1') {
// while문을 쓴 이유는 Pop한 요소가 이미 제거된 값이 아닐 때까지 계속하기 위해.
while (MaxPQ.GetLength()) {
const MaxPop = MaxPQ.Pop();
if (visited.get(MaxPop) > 0) {
visited.set(MaxPop, visited.get(MaxPop) - 1);
break;
}
}
} else {
while (MinPQ.GetLength()) {
const MinPop = MinPQ.Pop();
if (visited.get(MinPop) > 0) {
visited.set(MinPop, visited.get(MinPop) - 1);
break;
}
}
}
}
}
// 마지막 명령에 따라 우선순위 큐에 제거되지 않은 값이 있을 수 있기 때문에.
while (MaxPQ.GetLength() && visited.get(MaxPQ.GetMax()) === 0) {
MaxPQ.Pop();
}
let max = MaxPQ.GetMax();
while (MinPQ.GetLength() && visited.get(MinPQ.GetMin()) === 0) {
MinPQ.Pop();
}
let min = MinPQ.GetMin();
let answer = max === null && min === null ? 'EMPTY' : `${max} ${min}`;
return answer;
};
let answer = [];
for (let i = 0; i < TestCase; i++) {
answer.push(TestStart());
}
console.log(answer.join('\n'));
앞서 말했듯, 이 코드는 메모리 초과로 실패하게 된다.
💡2차 제출 코드 (Success)
질문 게시판에 있는 모든 반례 코드가 잘 동작하는 것을 확인했고,
이를 통해 입력 받는 부분을 의심하기 시작했다.
fs 를 이용하여 입력을 받는것이 아니라 readline으로 입력을 받도록 수정했다.
TestStart()함수 제거.- 최대힙과 최소힙 함수에 힙의 모든 값을 제거하는
Clear메서드 생성. index변수를 이용하여 몇번째 줄을 읽고 있는지 확인.EndLine변수로 현재 테스트 코드 마지막 줄을 체크.
전체 코드
const readline = require('readline')
const fs = require('fs')
const rl = readline.createInterface({
input: process.platform === 'linux' ? process.stdin : fs.createReadStream('./input.text'),
output: process.stdout,
terminal: false,
})
class MinHeap {
constructor() {
this.heap = [null];
}
Insert(item) {
let Current = this.heap.length;
while (Current > 1) {
const Parent = Math.floor(Current / 2);
if (this.heap[Parent] > item) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else break;
}
this.heap[Current] = item;
}
Pop() {
if (this.heap.length > 2) {
const PopItem = this.heap[1];
this.heap[1] = this.heap.pop();
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
while (this.heap[LeftChild]) {
let Compare = LeftChild;
if (this.heap[RightChild] && this.heap[LeftChild] > this.heap[RightChild]) {
Compare = RightChild;
}
if (this.heap[Current] > this.heap[Compare]) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
} else break;
}
return PopItem;
} else if (this.heap.length === 2) {
return this.heap.pop();
} else {
return null;
}
}
GetLength() {
return this.heap.length - 1;
}
GetMin() {
return this.heap.length > 1 ? this.heap[1] : null;
}
Clear() {
this.heap = [null];
}
}
class MaxHeap {
constructor() {
this.heap = [null];
}
Insert(item) {
let Current = this.heap.length;
while (Current > 1) {
const Parent = Math.floor(Current / 2);
if (this.heap[Parent] < item) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else break;
}
this.heap[Current] = item;
}
Pop() {
if (this.heap.length > 2) {
const PopItem = this.heap[1];
this.heap[1] = this.heap.pop();
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
while (this.heap[LeftChild]) {
let Compare = LeftChild;
if (this.heap[RightChild] && this.heap[LeftChild] < this.heap[RightChild]) {
Compare = RightChild;
}
if (this.heap[Current] < this.heap[Compare]) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
} else break;
}
return PopItem;
} else if (this.heap.length === 2) {
return this.heap.pop();
} else {
return null;
}
}
GetLength() {
return this.heap.length - 1;
}
GetMax() {
return this.heap.length > 1 ? this.heap[1] : null;
}
Clear() {
this.heap = [null];
}
}
const MinPQ = new MinHeap();
const MaxPQ = new MaxHeap();
let index = 0;
let EndLine = 0;
let visited = new Map();
let answer = [];
rl.on('line', (line) => {
// 첫번쨋줄을 읽으면
if (index === 0) {
index++;
return;
}
// 현재 인덱스가 더 크면, 새로운 테스트케이스라는 뜻
if (index > EndLine) {
// 새로운 테스트의 끝부분 체크.
EndLine = +line + index++;
// 변수 초기화.
MinPQ.Clear();
MaxPQ.Clear();
visited.clear();
return;
}
// 명령에 따라 행동 진행. (이전의 TestStart 함수와 동일)
const [Order, Num] = line.split(' ')
if (Order === 'I') {
const InsertItem = parseInt(Num);
MinPQ.Insert(InsertItem);
MaxPQ.Insert(InsertItem);
if (visited.has(InsertItem)) {
visited.set(InsertItem, visited.get(InsertItem) + 1);
} else {
visited.set(InsertItem, 1);
}
} else {
if (Num === '1') {
while (MaxPQ.GetLength()) {
const MaxPop = MaxPQ.Pop();
if (visited.get(MaxPop) > 0) {
visited.set(MaxPop, visited.get(MaxPop) - 1);
break;
}
}
} else {
while (MinPQ.GetLength()) {
const MinPop = MinPQ.Pop();
if (visited.get(MinPop) > 0) {
visited.set(MinPop, visited.get(MinPop) - 1);
break;
}
}
}
}
if (index === EndLine) {
while (MaxPQ.GetLength() && visited.get(MaxPQ.GetMax()) === 0) {
MaxPQ.Pop();
}
let max = MaxPQ.GetMax();
while (MinPQ.GetLength() && visited.get(MinPQ.GetMin()) === 0) {
MinPQ.Pop();
}
let min = MinPQ.GetMin();
answer.push(max === null && min === null ? 'EMPTY' : `${max} ${min}`);
}
index++
})
rl.on('close', () => {
console.log(answer.join('\n'))
})
이렇게 처음 코드를 readline으로 바꿔주면 무사히 통과할 수 있었다.
그런데 readline으로 바꾸는 과정에서 다른 사람들의 코드를 확인했는데 내 코드에서 수정하면 좋을 것 같아서 코드를 수정하기로 했다.
💡3차 제출 코드 (Success)
전체적인 로직은 바뀌는 것은 없다.
단지 기존 코드에서는 최소힙과 최대힙을 각각 구현하기 위해 거의 동일한 코드를 2번 작성하여 코드의 길이가 길어졌다.
따라서 Heap 을 생성할 때, 비교 함수CompareFunc을 함께 건내주어서 1개의 Heap 구현 코드로 최대힙, 최소힙을 모두 만들 수 있게 수정했다.
전체 코드
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
class Heap {
constructor(CompareFunc) {
this.heap = [null];
this.CompareFunc = CompareFunc;
}
Insert(item) {
let Current = this.heap.length;
while (Current > 1) {
const Parent = Math.floor(Current / 2);
if (this.CompareFunc(this.heap[Parent], item)) {
this.heap[Current] = this.heap[Parent];
Current = Parent;
} else break;
}
this.heap[Current] = item;
}
Pop() {
if (this.heap.length > 2) {
const PopItem = this.heap[1];
this.heap[1] = this.heap.pop();
let Current = 1;
let LeftChild = Current * 2;
let RightChild = Current * 2 + 1;
while (this.heap[LeftChild]) {
let Compare = LeftChild;
if (this.heap[RightChild] && this.CompareFunc(this.heap[LeftChild], this.heap[RightChild])) {
Compare = RightChild;
}
if (this.CompareFunc(this.heap[Current], this.heap[Compare])) {
[this.heap[Current], this.heap[Compare]] = [this.heap[Compare], this.heap[Current]];
Current = Compare;
LeftChild = Current * 2;
RightChild = Current * 2 + 1;
} else break;
}
return PopItem;
} else if (this.heap.length === 2) {
return this.heap.pop();
} else {
return null;
}
}
GetLength() {
return this.heap.length - 1;
}
GetMin() {
return this.heap.length > 1 ? this.heap[1] : null;
}
Clear() {
this.heap = [null];
}
}
const MinPQ = new Heap((a,b) => a > b);
const MaxPQ = new Heap((a,b) => a < b);
let index = 0;
let EndLine = 0;
let visited = new Map();
let answer = [];
rl.on('line', (line) => {
if (index === 0) {
index++;
return;
}
if (index > EndLine) {
EndLine = +line + index++;
MinPQ.Clear();
MaxPQ.Clear();
visited.clear();
return;
}
const [Order, Num] = line.split(' ')
if (Order === 'I') {
const InsertItem = parseInt(Num);
MinPQ.Insert(InsertItem);
MaxPQ.Insert(InsertItem);
if (visited.has(InsertItem)) {
visited.set(InsertItem, visited.get(InsertItem) + 1);
} else {
visited.set(InsertItem, 1);
}
} else {
if (Num === '1') {
while (MaxPQ.GetLength()) {
const MaxPop = MaxPQ.Pop();
if (visited.get(MaxPop) > 0) {
visited.set(MaxPop, visited.get(MaxPop) - 1);
break;
}
}
} else {
while (MinPQ.GetLength()) {
const MinPop = MinPQ.Pop();
if (visited.get(MinPop) > 0) {
visited.set(MinPop, visited.get(MinPop) - 1);
break;
}
}
}
}
if (index === EndLine) {
while (MaxPQ.GetLength() && visited.get(MaxPQ.GetMin()) === 0) {
MaxPQ.Pop();
}
let max = MaxPQ.GetMin();
while (MinPQ.GetLength() && visited.get(MinPQ.GetMin()) === 0) {
MinPQ.Pop();
}
let min = MinPQ.GetMin();
answer.push(max === null && min === null ? 'EMPTY' : `${max} ${min}`);
}
index++
})
rl.on('close', () => {
console.log(answer.join('\n'))
})
🧐 후기
오랜만에 우선순위 큐 문제를 풀었는데 생각했던 것보다 시간을 오래 잡아먹은 문제였다.
처음 로직이 실패한 후에 질문 게시판을 모두 훑어봤는데 모든 반례 예시의 정답이 잘 나왔다.
그 후에 다른 사람들의 풀이를 확인했는데 fs를 이용하여 통과하는 사람들이 있는 것을 보고 입력을 받는 부분 문제가 아니라고 생각해 더욱 미궁에 빠졌다. 결국 마지막에 포기하고 혹시나 하는 마음에 input을 readline을 이용하는 방법으로 수정했고 그제서야 통과하게 되었다.
최소힙 클래스를 생성하여 만들어서 사용하는 코드의 경우 readline으로 풀어야 메모리 초과가 나지 않는 것 같고,
만약 그냥 전역 변수의 빈배열과 전역 함수를 생성하여 배열을 관리하며, 테스트 케이스마다 배열을 초기화하는 방식으로 진행할 경우 그냥 fs를 써서 진행해도 통과가 가능한 것 같다.
JavaScript를 사용하는 모두를 위해...