[백준/그리디] 1931번. 회의실배정(JavaScript)

문제

이 문제의 시간제한은 2초로 

1초 당 간단한 연산을 1억번(10^8) 정도 계산할 수 있기 때문에

2초면 대략 2억번의 연산까지 허용된다고 생각하고 풀어야 한다.

 

완전탐색으로 풀었을 시 입력이 최대 10만(10^5)인데, 모든 경우의 수(N^2)를 구한 후 각 경우의 회의개수 중 최대 개수를 구할 수 있지만,

최악의 경우 10^5 x 10^5 = 10^10의 시간 복잡도가 요구되어 효율적이지 않다.

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

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

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

 

풀이

가능한 아이디어는 3가지가 있다.

1. 시작시간이 빠른 순서대로 정렬한다.

시작 시간이 빠르지만 회의시간이 긴 게 있다면, 최적의 최대 회의개수를 구할 수 없다.

 

2. 회의시간이 짧은 순서대로 정렬한다.

짧은 순서대로 배정한다고 하면, 위의 예시에서 3시~5시 회의가 가장 짧기 때문에 먼저 배정될 텐데,

그러면 1시~4시, 4시~7시 2개를 할 수 있음에도 불구하고, 3시~5시 1개의 회의만 진행할 수 있는 문제가 발생한다.

 

3. 종료시간이 빠른 순서대로 정렬한다.

이 경우는 반례 없이 문제의 답을 찾을 수 있다.

회의가 끝나야지만 다음회의가 진행될 수 있고, 가장 회의가 빨리 끝나는 것부터 선택하면,

최대 개수의 회의를 가질 수 있을 것이기 때문이다.

 

따라서 세가지 아이디어 중 종료 시간이 빠른 순서대로 정렬하는 아이디어를 사용한다.

종료 시간이 같을 경우에는, 시작 시간이 빨라야 회의실에 더 일찍 들어가 회의를 시작할 수 있으므로

시작 시간 오름차순으로 정렬한다. (매 순간마다 바로 시작할 수 있는 강의를 고른다.)

 

회의를 시작하기 위해서는 회의실에서 회의가 진행중이지 않아야하고,

회의가 진행 중이지 않기 위해서는 현재 시간이 종료 시간보다 뒤에 있어야한다.

즉, 현재 시간이 기존 종료 시간보다 뒤에 있다면 현재 시간 회의는 이뤄질 수 있으므로 정답에 추가한다.

 

 

코드는 다음과 같다.

const fs = require('fs');
const input = fs.readFileSync("../test.txt").toString().trim().split('\n');
const N = parseInt(input.shift(), 10);

function solution(N, input) {
    let time = new Array(N);
    for (let i = 0; i < N; i++) {
        let [start, end] = input[i].toString().trim().split(' ').map(Number);
        time.push([start, end]);
    }

    time.sort(function (a, b) { // 종료시간 기준으로 정렬
        if (a[1] === b[1]) { // 종료시간이 같으면 시작기준으로 정렬한다.
            return a[0] - b[0];
        } return a[1] - b[1];
    });

    let answer = 0;
    let end = 0;
    // let timetable = [];

    time.forEach(e => {
        if (end <= e[0]) { // 현재 시간이 기존 종료 시간보다 뒤에 있다면 현재 시간 회의는 이뤄질 수 있으므로 정답에 추가한다.
            answer += 1;
            // timetable.push([e[0], e[1]]);
            end = e[1];
        }
    });
    // console.log(timetable);
    return answer;
}

console.log(solution(N, input));