[BOJ] 19598 - 최소 회의실 개수 (Python, JavaScript)

 

 

아이디어

 

회의 시간을 정렬하여 회의 시간이 겹치면 회의실 수를 증가시킨다.

 

 

풀이 #1 (Python)

 

회의 시작 시간과 끝나는 시간을 튜플로 오름차순 정렬하여 리스트 meeting에 저장한다.

리스트 time은 회의가 끝나는 시간들을 최소 힙의 형태로 저장하며, 처음에는 첫 회의가 끝나는 시간을 저장한다.

 

for문에서는 두 번째 회의부터 시작 시간과 끝나는 시간을 각각 s와 e로, 가장 빨리 끝나는 이전 회의 시간을 t로 둔다.

e를 우선 time에 추가한 후 s와 t를 비교해 회의 시간이 겹치면 t를 다시 추가하고, 그렇지 않으면 t는 time에서 제거한다.

 

import sys, heapq

input = sys.stdin.readline

def solution():
    N = int(input())
    meeting = sorted([tuple(map(int, input().split())) for _ in range(N)])
    time = [meeting[0][1]]
    for i in range(1, N):
        s, e = meeting[i]
        t = heapq.heappop(time)
        heapq.heappush(time, e)
        if s < t:
            heapq.heappush(time, t)
    print(len(time))

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작하며, 자바스크립트는 우선순위 큐 내장 모듈이 없으므로 이를 직접 구현한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

class Heap {
    constructor() {
        this.tree = [-1];
    }
    
    heaplength() {
        return this.tree.length-1;
    }
    
    heappush(num) {
        this.tree.push(num);
        this.heapify(1);
    }
    
    heappop() {
        if (this.heaplength() > 0) {
            let tree = this.tree;
            [tree[1], tree[this.heaplength()]] = [tree[this.heaplength()], tree[1]];
            let temp = tree.pop();
            this.heapify(0);
            return temp;
        }
        return -1;
    }
    
    heapify(isPush) {
        let tree = this.tree;
        if (isPush) {
            let idx = this.heaplength();
            while (idx > 1) {
                let p = parseInt(idx/2)
                if (tree[idx] < tree[p]) [tree[idx], tree[p]] = [tree[p], tree[idx]];
                else return;
                idx = p;
            }
        }
        else {
            let idx = 1;
            while (idx*2 <= this.heaplength()) {
                let temp = idx*2;
                if (idx*2+1 <= this.heaplength()) {
                    if (tree[idx*2+1] < tree[temp]) temp = idx*2+1;
                }
                if (tree[temp] < tree[idx]) [tree[idx], tree[temp]] = [tree[temp], tree[idx]];
                idx = temp;
            }
        }
    }
}

const N = +input[0];
let meeting = [];
for (let i=1; i<=N; i++) {
    let [s, e] = input[i].split(' ').map(Number);
    meeting.push([s, e])
}
meeting.sort((a, b) => {
    if (a[0] === b[0]) return a[1]-b[1];
    return a[0]-b[0];
});
let time = new Heap();
time.heappush(meeting[0][1]);
for (let i=1; i<N; i++) {
    let [s, e] = meeting[i];
    let t = time.heappop();
    time.heappush(e);
    if (s < t) time.heappush(t);
}
console.log(time.heaplength());

 

 

 

풀이 #3 (JavaScript)

 

다른 분의 풀이를 참고하여 우선순위 큐 없이 문제를 풀 수 있었다.

 

리스트 meeting에 회의 시작 시간과 끝나는 시간을 각각 1, -1과 함께 저장한 후 오름차순 정렬한다.

for문에서 회의가 시작하면 cnt를 1 증가시키고, 회의가 끝나면 1 감소시켜 현재 열리고 있는 회의 수를 cnt에 저장한다.

결과값 res에 cnt의 최댓값을 저장해 나가고, 마지막에 최소 회의실 개수를 출력한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0];
let meeting = [];
for (let i=1; i<=N; i++) {
    let [s, e] = input[i].split(' ').map(Number);
    meeting.push([s, 1]);
    meeting.push([e, -1]);
}
meeting.sort((a, b) => {
    if (a[0] === b[0]) return a[1]-b[1];
    return a[0]-b[0];
})
let [res, cnt] = [0, 0];
for (let i=0; i<N*2; i++) {
    cnt += meeting[i][1];
    if (cnt > res) res = cnt;
}
console.log(res);