백준[JS] > 11000번 강의실 배정

 

 

문제링크

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

 

제출코드 

일단 수업들을 시작시간이 빠른순으로 정렬하고 시작시간이 같으면 끝나는 시간이 빠른시간 순으로 정렬하였다.

그리고 정렬한 수업들을 순회하면서 최소 힙과 비교하면서(힙을 안쓰고 정렬을 이용하면 연산횟수가 기하급수적으로 많아서 시간초과가 발생한다.) 비어있는 강의실이 없는 경우 힙에 새롭게 추가하였다. 여기서 추가할 때 수업의 끝나는 시간만 힙에 추가했다. ( 우리가 필요한 정보는 수업이 끝나는 시간이기 때문이다. )

마지막에 힙의 사이즈를 통해 몇개의 강의실이 쓰였는 지 알 수 있다.

참고) 자바스크립트에서는 힙 자료구조를 직접 구현해야 한다.

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

    insert(v) {
        let heap = this.heap;
        heap.push(v);

        let childIdx = heap.length - 1;
        let parentIdx = parseInt((childIdx - 1) / 2);

        while (childIdx >= 1 && heap[childIdx] < heap[parentIdx]) {
            this.swap(parentIdx, childIdx);
            childIdx = parentIdx;
            parentIdx = parseInt((childIdx - 1) / 2);
        }
    }

    replace(v) {
        let heap = this.heap;
        heap[0] = v;

        let parentIdx = 0;
        let child1Idx = 1;
        let child2Idx = 2;

        while (
            (heap[child1Idx] !== undefined && heap[child1Idx] < heap[parentIdx]) ||
            (heap[child2Idx] !== undefined && heap[child2Idx] < heap[parentIdx])
        ) {
            if (heap[child2Idx] !== undefined) {
                // child1, child2 둘다 있는 경우
                let minIdx = heap[child1Idx] < heap[child2Idx] ? child1Idx : child2Idx;
                this.swap(parentIdx, minIdx);

                parentIdx = minIdx;
                child1Idx = parentIdx * 2 + 1;
                child2Idx = parentIdx * 2 + 2;
            } else {
                //child1만 있는 경우
                this.swap(parentIdx, child1Idx);
                break;
            }
        }
    }

    swap(parentIdx, childIdx) {
        let temp = this.heap[parentIdx];
        this.heap[parentIdx] = this.heap[childIdx];
        this.heap[childIdx] = temp;
    }

    getSize() {
        return this.heap.length;
    }
}

const inputs = require("fs")
    .readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const n = +inputs[0];
const lecture = [];

for (let i = 1; i < inputs.length; i++) {
    const l = inputs[i].split(" ").map((n) => Number(n));
    lecture.push(l);
}

lecture.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));

const minHeap = new MinHeap();

minHeap.insert(lecture[0][1]);

for (let i = 1; i < n; i++) {
    const [start, finish] = lecture[i];

    if (minHeap.heap[0] <= start) {
        minHeap.replace(finish);
    } else {
        minHeap.insert(finish);
    }
}

console.log(minHeap.getSize());