[JS] 백준 1931번 : 회의실 배정 - 그리디

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

1931번: 회의실 배정

 

📋풀이방법

1. 문제를 봤을때 그리디(탐욕법)문제인 것을 알아야한다.

2. 회의가 빨리 끝나는 것들로 진행이 되어야 최대한 많이 할 수 있다.

3. 이 때 회의가 빨리 끝나는 시간으로 정렬할 때 어떤 기준으로 빨리 끝남을 정렬할 지 알아내야한다.

 -시작시간을 기준으로 정렬을 했을 때는 회의시간이 짧은 것들을 진행할 수 없을 가능성이 생기게된다.

 -회의시간이 짧을 순으로 정렬하면 아래와 같이 애매하게 시작시간과 끝나는 시간으로인해 사용할 수 있는 최대의 회의 갯수가 되지 못한다.

4. 그래서 정렬을 할 때 회의가 끝나는 시간을 기준으로 해야한다.

5. 정렬을 끝나는 기준으로 완료했다면 정렬된 회의시간을 기준으로 가능한 회의를 계산한다.

 

6.오름차순된 회의시간을 차례로 검사하면서 현재 진행중인 회의시간의 끝나는 타임을 endtime으로 저장하면서 그 끝나는 시간에 맞는 회의인지를 검사한다.

 -끝나는 시간을 0부터 시작해 빨리끝나는 회의 순으로 첫 번째 회의의 끝나는 시간을 endtime에 저장한다.

 -이후 회의가 끝나는 시간에 맞춰서 혹은 그보다 이후에 희의가 시작 가능하다면 그 회의를 진행하고 다시 두번째 회의의 끝나는 시간을 endtime에 저장한다. - 다음 회의의 시작시간을 조건으로 검사

 -이렇게 되는 이유는 앞에서 끝나는 시간을 기준으로 정렬을 했기 때문이다.

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let N=Number(input.shift());
let arr=[];
for(var i=0;i<N;i++){
    let [s,e]=input.shift().split(" ").map(Number);
    arr.push([s,e]);
}

arr.sort((a,b)=>{
    if(a[1]==b[1]) return a[0]-b[0]; 
    else return a[1]-b[1]
});
let answer=0;
let et=0;
for(var i of arr){
    if(i[0]>=et){
        answer++;
        et=i[1];
    }
}
console.log(answer)

 

 

💢어려웠던 점

1. 정렬해야하는 것을 알았지만 어떤 기준으로 정렬해야할 지 몰랐다.

 -회의시간이 그저 짧은 순으로 하려고 했지만 이는 위에서 말한 조건때문에 맞지않았다.

2. 정렬 후에 어떻게 회의를 진행했음을 표시하고 카운팅할지 구현해내지 못했다.

 -endtime이라는 변수로 끝나는 시간을 저장하면서 다음 회의가 endtime보다 크거나 같으면 진행하게끔 했다.