[백준] 1931. 회의실 배정 (자바스크립트/js/javascript/node.js/정렬/그리디 알고리즘/탐욕적 알고리즘)

 

문제를 풀기 위한 아이디어

시간 제한은 2초이므로 대략 2억번의 연산까지 허용된다고 생각하고 풀어야 한다.

정확한 답을 구해내려면 완전탐색 유형으로 접근하여 모든 경우의 수를 다 따져본 후 가장 최선의 답을 고르면 되겠지만, 입력이 최대 10만이므로 이 방법은 효율적이지 않다.

따라서 위의 문제를 풀기 위해서는 현재 상황에서 지금 당장 좋은 것만 고르는 그리디 알고리즘으로 풀어야 한다.

그리디 알고리즘이 언제나 최적의 해를 보장하는 것은 아니지만 많은 문제에 대한 해를 보다 효율적으로 구해낼 수 있다. 

위의 문제는 그리디 알고리즘의 대표적인 유형 중 하나인 활동선택 문제에 해당한다.

 

* 활동 선택 문제 : 한 번에 하나의 활동만 처리할 수 있는 하나의 강의실에서 제안된 활동들 중 가장 많은 활동을 처리할 수 있는 스케줄을 짜는 문제

 

따라서 이 문제에서는, 회의 시간이 빨리 끝나는 순으로 정렬 (끝나는 시간이 같다면 빨리 시작하는 순으로 정렬) 하여 매 순간마다 바로 시작할 수 있는 강의를 고르는 것이다.

반복문을 돌며 진행한다. 이 때 이전 회의 시간이 끝나야 다음 회의를 진행할 수 있으므로, 이전 회의 종료 시간보다 현재 반복문을 돌고 있는 회의의 시작시간이 빨리 시작하면 넘어간다. 그렇지 않다면 회의가 진행되는 것이고 count를 1 증가 시키면 된다.

---

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const N = Number(input[0]);
input.shift();
input = input.map((element) => element.split(" "));
input.sort((a, b) => {
  // 회의가 끝나는 시간을 기준으로 정렬, 끝나는 시간이 같다면 일찍 시작하는 순으로 정렬
  a[0] = Number(a[0]);
  a[1] = Number(a[1]);
  b[0] = Number(b[0]);
  b[1] = Number(b[1]);

  if (a[1] === b[1]) {
    return a[0] - b[0];
  }
  return a[1] - b[1];
});

let count = 0;
let previousEnd = 0;
let currentStart;
let currentEnd;
for (let i = 0; i < N; i++) {
  currentStart = input[i][0];
  currentEnd = input[i][1];
  if (currentStart < previousEnd) {
    // 현재 회의 시작시간이 이전 회의 종료시간보다 일찍 시작하면 넘어가기
    continue;
  } else {
    count++;
  }
  previousEnd = currentEnd;
}

console.log(count);