[바미] 회의실 배정

문제

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

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = parseInt(input[0], 10);
const meetings = input.slice(1).map(line => line.split(' ').map(Number));

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

let count = 0;
let lastEndTime = 0;

for (let i = 0; i < N; i++) {
    const [start, end] = meetings[i];
    if (start >= lastEndTime) {
        count++;
        lastEndTime = end;
    }
}

console.log(count);

문제 해설

문제의 목표는 회의실에서 최대한 많은 회의를 겹치지 않게 배치하는 것인데 이를 위해 회의를 선택할 때, 종료 시간이 가장 빠른 회의를 먼저 선택하는 방향으로 풀어볼 수 있습니다. 이렇게 하면 더 많은 회의를 수용할 수 있는 가능성이 높아지기 때문이죠.

마찬가지로 이 문제도 그리디 알고리즘을 사용하여 푸는 알고리즘이 되겠습니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

주어진 회의를 정렬하는 데 소요되는 시간은 O(NlogN)이 걸리고, 정렬된 회의를 한 번 순회하면서 회의 수를 세는 데 소요되는 시간이 O(N)이 걸립니다.

 

따라서 전체 시간 복잡도는 O(N log N)이 소요됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

주어진 회의 정보를 저장하는 데 필요한 O(N)만큼의 공간만 차지하기 때문에 전체 공간 복잡도는 O(N)이 됩니다.