[JavaScript] 백준 19598 최소 회의실 개수 (JS)

최소 회의실 개수

📚 문제 설명

N 개의 회의가 있다. 각각의 회의 시작 시간과 종료 시간이 주어질 때, 필요한 강의실의 최소 갯수를 찾아라.
단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

👨🏻‍💻 풀이 과정

이 문제는 이전에 풀었던 강의실 문제와 거의 완전히 똑같은 문제이다.

따라서 해당 문제 풀이에 대한 자세한 설명과 Priority Queue 구현에 대한 설명은 강의실 문제를 참고.

• 회의를 시작순으로 정렬.
• 회의가 끝나는 시간이 빠른 순으로 보여주는 Priority Queue PQ를 생성.
• 회의 시작 시간을 확인, PQ를 이용해 가장 빨리 끝나는 강의실 시간과 비교.
• 만약 시작 시간이 더 클 경우 PQ에서 Pop() 진행.
• 필요한 회의실의 수는 최종 PQ의 길이.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = input.shift();
    input = input.map(v => v.split(' ').map(Number));
    input.sort((a, b) => a[0] - b[0]);
	// Min Heap을 이용한 Priority Queue 구현
    class MINHEAP {
        constructor() {
            this.heap = [null];
        }

        Insert(item) {
            let cur = this.heap.length;
            if (this.heap.length > 1) {
                while (cur > 1) {
                    const PARENT = Math.floor(cur / 2);
                    if (this.heap[PARENT] > item) {
                        this.heap[cur] = this.heap[PARENT];
                        cur = PARENT;
                    }else break;
                }
            }
            this.heap[cur] = item;
        }

        Pop() {
            if (this.heap.length > 2) {
                let PopElement = 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 CompareChild = LeftChild;
                    if (this.heap[RightChild] && this.heap[LeftChild] > this.heap[RightChild]) {
                        CompareChild = RightChild;
                    }
                    if (this.heap[CompareChild] < this.heap[Current]) {
                        [this.heap[Current], this.heap[CompareChild]] = [this.heap[CompareChild], this.heap[Current]];
                        Current = CompareChild;
                    }else break;
                    LeftChild = Current * 2;
                    RightChild = Current * 2 + 1;
                }
                return PopElement;
            }else if (this.heap.length === 2) {
                return this.heap.pop();
            } else {
                return null;
            }
        }

        GetMin() {
            return this.heap[1];
        }

        GetLength(){
            return this.heap.length - 1;
        }
    }
	
    const solution = (INPUT) => {
        const PQ = new MINHEAP();
        for (let i = 0; i < INPUT.length; i++) {
            const [START, END] = INPUT[i];
          // 만약 PQ에 값이 있다면 비교 진행
            if (PQ.GetLength()) {
                if (PQ.GetMin() <= START) {
                    PQ.Pop();
                }
                PQ.Insert(END);
              //PQ에 값이 없다면 Push
            } else {
                PQ.Insert(END);
            }
        }
        console.log(PQ.GetLength());
    };
    solution(input);

🧐 후기

이전에 풀었던 강의실 문제를 다시 복습할 수 있었던 문제이다.
이전에 강의실 문제를 풀 때 오랫동안 고민을 해서 그런지 이번 문제를 풀 때는 풀이를 생각할 때 정말 금방 생각할 수 있었다.