백준[JS] > 7762번 이중 우선순위 큐

문제링크

https://www.acmicpc.net/problem/7662

문제풀이

나는 이 문제를 풀기 위해 최대힙, 최소힙을 만들고 실제로 힙에 존재해야 할 숫자들을 Map 객체로 관리하였다.

( Primary Queue 를 자바스크립트로 구현하기 위해선 직접 Class 객체를 만들어야 해서 어쩔 수 없이 코드가 길어진 점 이해 부탁드립니다. ) 

 

연산 과정은 이러하다. 

 

- I 연산일 때는 최대 힙, 최소 힙에 숫자를 넣었고 

- D 1 연산일 때는 최대힙에서 최대 숫자를 뽑고

- D -1 연산일 때는 최소힙에서 최소 숫자를 뽑았다. 

- I 연산으로 숫자를 넣을 때는 map 객체에서 해당 숫자의 갯수를 +1

- D 연산으로 숫자를 뺄 때는 map 객체에서 해당 숫자의 갯수를 -1 

 

이런 과정을 거치면 힙에 들어있는 숫자가 실제로 유효한 숫자인지 map 객체를 통해 알 수 있기 때문에 모든 연산이 끝났을 때 최댓값, 최솟값을 구할 수 있다. 

const readline = require("readline");
const rl = readline.createInterface({
    input: process.platform === "linux" ? process.stdin : fs.createReadStream("./input.text"),
    output: process.stdout,
});

class Heap {
    constructor(compareFn) {
        this.heap = [];
        this.compareFn = compareFn;
    }

    insert(n) {
        let heap = this.heap;

        heap.push(n);

        if (heap.length > 1) {
            let childIdx = heap.length - 1;
            let parentIdx = Math.floor((childIdx - 1) / 2);

            while (childIdx !== 0) {
                if (this.compareFn(heap[parentIdx], heap[childIdx])) {
                    break;
                }

                [heap[parentIdx], heap[childIdx]] = [heap[childIdx], heap[parentIdx]];
                childIdx = parentIdx;
                parentIdx = Math.floor((childIdx - 1) / 2);
            }
        }
    }

    pop() {
        let heap = this.heap;

        if (heap.length === 0) {
            return null;
        } else if (heap.length === 1) {
            return heap.pop();
        } else {
            let popped = heap[0];
            heap[0] = heap.pop();

            let parentIdx = 0;

            while (parentIdx * 2 + 1 < heap.length) {
                let childIdx = parentIdx * 2 + 1;

                if (childIdx + 1 < heap.length && this.compareFn(heap[childIdx + 1], heap[childIdx])) {
                    childIdx += 1;
                }

                if (this.compareFn(heap[parentIdx], heap[childIdx])) {
                    break;
                }

                [heap[parentIdx], heap[childIdx]] = [heap[childIdx], heap[parentIdx]];

                parentIdx = childIdx;
            }

            return popped;
        }
    }
}

let maxHeap = new Heap((parent, child) => {
    if (parent > child) {
        return true;
    } else {
        return false;
    }
});
let minHeap = new Heap((parent, child) => {
    if (parent < child) {
        return true;
    } else {
        return false;
    }
});
let map = new Map();

let answer = "";

let index = 0;
let opCnt = 0;
let lastOpIndex = 0;

rl.on("line", (line) => {
    if (index === 0) {
        ++index;
        return;
    }

    if (line.split(" ").length === 1) {
        maxHeap.heap = [];
        minHeap.heap = [];
        map.clear();
        lastOpIndex = index + Number(line);
        ++index;
        return;
    }

    let [op, v] = line.split(" ");
    if (op === "I") {
        let insertNum = Number(v);
        maxHeap.insert(insertNum);
        minHeap.insert(insertNum);

        if (map.has(insertNum)) {
            map.set(insertNum, map.get(insertNum) + 1);
        } else {
            map.set(insertNum, 1);
        }
    } else {
        if (v === "1") {
            while (maxHeap.heap.length) {
                let popped = maxHeap.pop();

                if (map.get(popped) >= 1) {
                    map.set(popped, map.get(popped) - 1);
                    break;
                }
            }
        } else if (v === "-1") {
            while (minHeap.heap.length) {
                let popped = minHeap.pop();

                if (map.get(popped) >= 1) {
                    map.set(popped, map.get(popped) - 1);

                    break;
                }
            }
        }
    }

    if (index === lastOpIndex) {
        let max = undefined;
        while (maxHeap.heap.length) {
            let popped = maxHeap.pop();

            if (map.get(popped) >= 1) {
                max = popped;
                break;
            }
        }
        let min = undefined;
        while (minHeap.heap.length) {
            let popped = minHeap.pop();

            if (map.get(popped) >= 1) {
                min = popped;
                break;
            }
        }

        if (max !== undefined || min !== undefined) {
            max = max !== undefined ? max : min;
            min = min !== undefined ? min : max;
            answer += `${max} ${min}\n`;
        } else {
            answer += "EMPTY\n";
        }
    }

    ++index;
});

rl.on("close", () => {
    console.log(answer.trim());
});

문제후기

메모리를 최적화를 위해 fs 모듈이 아닌 readline을 이용했고 최대힙, 최소힙을 하나의 Heap 클래스에 하나의 인자를 주어 각각의 인스턴스를 만들었다. 처음 접해보는 문제 유형이라 고민하는 시간을 많이 가졌고 다른 분들의 풀이도 참고하는 좋은 시간이었다.