3 February 2025 / ALGORITHM, JAVASCRIPT

백준 21939 문제 추천 시스템 Version 1

문제 추천 시스템 Version 1

recommend(x) : x 가 1이면 난이도 가장 높은 문제를 우선순위 큐에서 출력, x 가 -1 이면 난이도가 가장 쉬운 문제를 출력.

→ 우선 순위큐를 minHeap, maxHeap 두 개를 써야겠다!
add(P, L) : 문제 번호가 P, 난이도가 L 인 문제를 추가

→ 2개의 우선순위 큐에 전부 넣어야한다.
solved(P) : 문제 번호가 P인 문제를 풀었다는 의미이므로, recommend 를 할 때 풀었던 문제는 추천하지 않도록 어딘가에 저장해두어야 함.

이 문제는 우선순위 큐와 Map 혹은 Object 를 쓰면 쉽게 풀리는 문제다.

문제가 Solved 되면 Map 혹은 Object 에 기억해뒀다가, recommend 명령어에 의해서 문제를 추천할 때 Solved 된 문제라면 다음 Min (혹은 Max) Heap 에서 하나를 더 꺼내면 된다.

그래서 문제 난이도가 그렇게 높게 잡히지는 않았는데 문제는 javascript 에 우선순위 큐가 없다는 점이다.

추가로 PriorityQueue 의 heap 을 일반 배열이 아닌 Queue 를 직접 구현했는데, 문제를 풀면서 heap 에 직접 shift 를 해야하는 경우가 필요하다고 착각했다. dequeue 를 여러 번 하면 되는 일이었는데.

자바스크립트는 배열의 shift 가 O(1) 이 아닌 O(n) 이다보니, shift 를 하려면 Queue 를 직접 구현해야해서 사용하면서도 일반 배열처럼 사용할 수 있는 방법을 고민하면서 풀었다.

javascript
class Queue {
    get(index){
        return this.items[index + this.head];
    }

    set(index,  value){
        this.items[index + this.head] = value;
    }
}

Queue 에 배열처럼 index 만으로 접근하고 싶었는데 내가 만든 Queue 는 head 와 tail 로 이동하기 때문에 head 로 인덱스의 값을 보정해야했다.

덕분에 모든 자료구조를 다 직접 짜면서 하다보니 코드가 엄청나게 길어졌다.

아래는 삽질한 코드이다..

javascript
class Problem {
    constructor(num, level) {
        this.num = num;
        this.level = level;
    }
}

class PriorityQueue {
    heap = new Queue();

    constructor(comparator) {
        if(comparator) this.comparator = comparator.bind(this);
        else this.comparator = (a, b) => this.heap.get(a) - this.heap.get(b);
    }

    enqueue(value){
        const heapLength = this.heap.push(value);
        this.bubbleUp(heapLength - 1);
    }

    peek(){
        return this.heap.get(0);
    }

    dequeue(){
        if(this.isEmpty()) return undefined;

        const root = this.heap.get(0);
        const leap = this.heap.pop();
        if(this.isEmpty()) return root;
        this.heap.set(0, leap);
        this.bubbleDown(0);

        return root;
    }

    bubbleUp(index_){
        let index = index_;
        while(index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if(this.comparator(index, parentIndex) >= 0) break;
            this.swap(index, parentIndex);
            index = parentIndex;
        }
        return index;
    }

    bubbleDown(index_){
        let index = index_;
        let smallestIndex = index;
        while(smallestIndex < this.heap.length){

            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;

            if(leftChildIndex < this.heap.length && this.comparator(leftChildIndex, smallestIndex) < 0){
                smallestIndex = leftChildIndex;
            }
            if(rightChildIndex < this.heap.length && this.comparator(rightChildIndex, smallestIndex) < 0){
                smallestIndex = rightChildIndex;
            }

            if(smallestIndex === index) break;
            this.swap(index, smallestIndex);
            index = smallestIndex;
        }
        return index;
    }

    isEmpty(){
        return this.heap.length === 0;
    }

    swap(i, j){
        const restore = this.heap.get(i);
        this.heap.set(i, this.heap.get(j));
        this.heap.set(j, restore);
    }
}

class Queue {
    items = {}
    head = 0;
    tail = 0;

    get length(){
        return this.tail - this.head;
    }

    get(index){
        return this.items[index + this.head];
    }

    set(index,  value){
        this.items[index + this.head] = value;
    }

    constructor() {}

    push(value){
        this.items[this.tail] = value;
        this.tail += 1;
        return this.length;
    }

    pop(){
        if(this.isEmpty()) return undefined;
        const leaf = this.items[this.tail - 1];
        delete this.items[this.tail - 1];

        if(!this.isEmpty()) this.tail -= 1;
        return leaf;
    }

    isEmpty(){
        if(this.head !== this.tail) return false

        this.head = this.tail = 0;
        return true

    }
}

class ProblemPriorityQueue extends PriorityQueue {
    solvedProblems = {}
    constructor(comparator) {
        super(comparator);
    }
    solved(index){
        this.solvedProblems[index] = true;
    }

    peek(){
        this.removeSolvedProblem();
        return super.peek();
    }

    removeSolvedProblem(){
        let peek = super.peek();
        while(peek.num in this.solvedProblems){
            super.dequeue();
            delete this.solvedProblems[peek.num];
            peek = super.peek();
        }
    }
}

function minComparator(a, b){
    if(this.heap.get(a).level !== this.heap.get(b).level) return this.heap.get(a).level - this.heap.get(b).level;
    return this.heap.get(a).num - this.heap.get(b).num;
}

function maxComparator(a, b){
    if(this.heap.get(a).level !== this.heap.get(b).level) return this.heap.get(b).level - this.heap.get(a).level;
    return this.heap.get(b).num - this.heap.get(a).num;
}

function add(P, L){
    minPPQ.enqueue(new Problem(P, L));
    maxPPQ.enqueue(new Problem(P, L));
}

function solved(P) {
    minPPQ.solved(P);
    maxPPQ.solved(P);
}

function recommend(x){
    if(x === -1) {
        return minPPQ.peek().num;
    } else {
        return maxPPQ.peek().num;
    }
}

const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let N = -1;
let M = -1;
let count = -1;
let answer = [];
const minPPQ = new ProblemPriorityQueue(minComparator);
const maxPPQ = new ProblemPriorityQueue(maxComparator);

rl.on("line", (line) => {
    if(N === -1){
        N = parseInt(line);
        count = N;
    } else if (count > 0) {
        const [num, level] = line.split(' ').map((n) => parseInt(n))
        add(num, level);
        count -= 1;
    } else {
        if(M === -1) M = parseInt(line);
        else {
            const [cmd, num1, num2] = line.split(' ');
            if (cmd === 'recommend') {
                const log = recommend(parseInt(num1));
                answer.push(log);
            } else if (cmd === 'solved') {
                solved(parseInt(num1));
            } else {
                add(parseInt(num1), parseInt(num2))
            }
        }
    }
}).on("close", () => {
    console.log(answer.join('\n'));
})

Subscribe to hoeeeeeh

Subscribe to hoeeeeeh