[JavaScript/Greedy] 백준 골드 5 : 11000 - 강의실 배정

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

11000번: 강의실 배정

---

📌 작성한 코드 1 (시간 초과)

// 시간 초과
const N = Number(input[0]);
const study = [];
for (let i = 1; i <= N; i++) {
    study.push(input[i].split(" ").map(Number));
}

study.sort((a, b) => {
    if (a[0] < b[0]) return -1;
    else if (a[0] > b[0]) return 1;
    else {
        if (a[1] < a[1]) return -1;
        else return 1;
    }
});

const room = [0];
for (let i = 0; i < N; i++) {
    let flag = false;
    for (let j = 0; j < room.length; j++) {
        if (room[j] <= study[i][0]) {
            room[j] = study[i][1];
            flag = true;
            break;
        }
    }
    if (!flag) room.push(study[i][1]);
}

console.log(room.length);

 

강의들을 시간별로 정렬하고 하나씩 확인하면서 현재 존재하는 교실에 들어갈 수 있다면 해당 교실의 값을 끝나는 시간으로 업데이트 하고, 들어갈 수 없다면 새로운 교실을 추가하는 방식으로 필요한 최소의 교실 수를 구하였다. 그러나 정렬하는데 NLogN + 이중 포문 N^2을 사용하면서 81% 정도에 시간 초과가 발생하였다.

---

📌 작성한 코드 2 (참고) 

// 11000
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input[0]);
const study = [];
for (let i = 1; i <= N; i++) {
    const [start, end] = input[i].split(" ").map(Number);
    study.push([start, 1]);
    study.push([end, -1]);
}

study.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

let answer = 0;
let room = 0;

for (let i = 0; i < study.length; i++) {
    room += study[i][1];
    answer = Math.max(answer, room);
}

console.log(answer);

첫번째 코드에서 시간을 더 줄 일 수 있는 방법을 찾다가 아예 다른 아이디어가 필요하다는 생각이 들어서 다른 분들의 풀이를 참고하게 되었다. 그렇게 얻게 된 아이디어는 `진행되는 강의수가 가장 많은 시간 대에 필요한 강의의 수`가 최소 강의실의 수라는 것이었다. 특정 시간대에 수업이 5개가 진행된다면, 해당 수업을 진행하기 위해서는 무조건 5개의 강의실이 필요하다. 그리고 다른 시간대에서는 같은 시간대에 겹치는 수업이 5개 이하라는 의미니까, 5개의 강의실이 있을 때 충분히 모든 수업을 진행할 수 있다. -> 그러므로 구해야 하는 것은 특정 시간대에 동시에 진행되는 강의의 수 중 최댓값을 찾으면 된다.

 

✅ 성공