자바스크립트 코딩테스트 강좌, 회의실 배정하기

2023년 10월 10일

문제 설명

회의실을 효율적으로 배정하는 것은 현대 사무 환경에서 중요한 문제입니다. 주어진 회의 목록에 대해 각 회의의 시작 시간과 끝 시간이 주어지면, 중복되지 않도록 최대한 많은 회의를 회의실에 배정하는 알고리즘을 작성하는 문제입니다.

입력:

meetings: 2차원 배열로 각 배열은 [startTime, endTime]으로 구성되어 있습니다.

출력:

배정할 수 있는 최대 회의 수

예시

예를 들어, 아래와 같은 회의 목록이 있다고 가정합시다.


            [[0, 30], [5, 10], [15, 20]]

여기서 배정할 수 있는 최대 회의 수는 2입니다. (회의 [0, 30]은 [5, 10] 및 [15, 20]과 겹치지 않음).

문제 접근 방법

이 문제는 그리디 알고리즘을 통해 해결할 수 있습니다. 회의를 끝나는 시간 기준으로 정렬한 후, 가장 일찍 끝나는 회의에 대해 회의를 배정하는 방식을 사용할 것입니다. 이 방식을 통해 회의실의 자원을 최대한 활용할 수 있습니다.

우선, 회의 목록을 끝나는 시간 기준으로 정렬합니다.
첫 번째 회의를 선택하고, 이후 회의가 시작되는 시간이 현재 선택된 회의의 끝나는 시간보다 클 경우 새로운 회의를 선택합니다.
이 과정을 회의 목록의 끝까지 반복합니다.

자바스크립트 구현

이제 위의 접근 방법을 바탕으로 자바스크립트 코드로 구현해 보겠습니다.


function maximumMeetings(meetings) {
    // 회의의 끝나는 시간으로 정렬
    meetings.sort((a, b) => a[1] - b[1]);
    
    let count = 0;
    let lastEndTime = 0;

    for (let i = 0; i < meetings.length; i++) {
        // 현재 회의의 시작 시간이 마지막으로 선택된 회의의 끝나는 시간보다 클 경우
        if (meetings[i][0] >= lastEndTime) {
            count++;
            lastEndTime = meetings[i][1]; // 마지막으로 선택한 회의의 끝나는 시간 업데이트
        }
    }

    return count;
}

// 테스트를 위한 예시
const testMeetings = [[0, 30], [5, 10], [15, 20]];
console.log(maximumMeetings(testMeetings)); // 출력: 2

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n log n)입니다. 이는 회의를 정렬하는 데에 소요되는 시간 때문입니다. 정렬된 회의 목록을 통해 최대 회의 수를 세는 과정은 O(n)입니다. 따라서 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 O(1)로, 정렬된 리스트를 사용하더라도 추가 공간을 필요로 하지 않습니다.

결론

“회의실 배정하기” 문제는 그리디 알고리즘을 통해 효율적으로 해결할 수 있는 대표적인 문제입니다. 이 문제를 통해 회의의 중복을 피하고 자원을 최대한 활용하는 방법을 배울 수 있습니다. 자바스크립트로 구현한 위의 코드는 이 문제를 해결하는 데 도움을 줄 수 있습니다. 이를 바탕으로 더 나아가 다양한 알고리즘 문제를 해결하는 데 필요한 기초를 다질 수 있을 것입니다.

문제 설명

예시

문제 접근 방법

자바스크립트 구현

복잡도 분석

결론

관련