[백준]JavaScript(nodejs) 1931번 '회의실 배정' 문제 풀이

백준 javascript(node js) 1931번 회의실 배정 문제 풀이

📖 들어가며

자바스크립트(nodejs)로 백준 1931번 문제인 그리디 알고리즘을 사용하여 '회의실 배정' 문제를 풀이해보겠다.

❓ 문제 

문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

• 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1

4

💡 풀이

그리디 알고리즘 문제다. 조금만 생각하면 쉬운 문제인 것 같다.

시작 시간이 빠르지만 끝나는 시간이 너무 늦어버리면 다음 회의를 하지 못하는 경우가 생길 수 있다.

그래서 최대한 회의실을 사용하기 위해서는 끝나는 시간이 빨라야 한다. 그래야 다음 회의들을 최대한 이용할 수 있다.

주의사항으로 회의실을 이용하는 시간은 겹칠 수 없다는 점도 유의한다.

 

먼저 입력 받은 배열을 끝나는 시간 기준으로 오름차순 정렬을 해준다. 대신에 끝나는 시간이 같을 경우 시작 시간 기준으로 오름차순 정렬을 해준다. 끝나는 시간이 같을 경우에는 일찍 시작을 해야 최대한 더 많이 이용을 할 수 있다.

 

이제 정렬된 값들을 순회하기 전에 et라는 변수를 0으로 초기화해줬는데, 이 변수는 최근에 회의실을 이용하고 끝나는 시간을 저장할 변수다. 0으로 초기화 함으로써 정렬된 배열을 순회할 때 최소 1개 이상의 회의실을 이용할 수 있게 끔 해주었다.

 

이제 정렬된 배열들을 forEach문을 돌리는데 시작시간이 변수 et(최근에 회의실이 끝난 시간)의 값보다 크거나 같다면 answer의 값을 증가 시키면서 회의실을 이용한 횟수를 누적시켜주고, 변수 et에 이용한 회의실의 끝나는 시간을 저장시켜주면서 정렬된 배열들을 검사하게 된다.

 

풀이 코드

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

const [n, ...arr] = input;
let answer = 0;
const times = arr
  .map((num) => num.split(' ').map((num) => +num))
  .sort((a, b) => {
    if (a[1] === b[1]) {
      return a[0] - b[0];
    } else {
      return a[1] - b[1];
    }
  });

let et = 0;
times.forEach((time) => {
  if (time[0] >= et) {
    answer++;
    et = time[1];
  }
});

console.log(answer);

✔ 채점

제출 결과