스위프트 코딩테스트 강좌, 회의실 배정하기

문제 설명

회의실 관리 시스템은 여러 개의 회의실을 효율적으로 사용할 수 있도록 회의 일정에 따라 회의실을 배정하는 프로세스입니다. 주어진 회의의 시작 시간과 종료 시간이 주어질 때, 회의실을 최대한 효율적으로 배정할 수 있는 방법을 제시하세요.

특정 회의가 시작될 때, 다른 회의가 진행 중이지 않은 회의실을 찾아야 합니다. 회의실 배정 문제는 다음과 같은 입력을 포함합니다:

회의의 수 n
회의의 시작 및 종료 시간을 포함한 배열 meetings로, 각 회의는 시작 시간과 종료 시간으로 구성됩니다.

입력

n = 3
meetings = [(0, 30), (5, 10), (15, 20)]

출력

회의실 수: 2

문제 해결 접근법

이 문제를 해결하기 위해 다음 단계를 따르겠습니다:

회의의 시작 시간과 종료 시간을 기준으로 회의가 끝나는 시간을 정렬합니다.
각 회의를 반복하면서, 현재 회의의 시작 시간과 이전 회의의 종료 시간을 비교합니다.
회의실이 필요할 경우 회의실의 수를 증가시키고, 회의가 끝나면 해당 회의실을 해제합니다.

알고리즘 구현

스위프트를 이용하여 회의실 배정 문제를 해결하는 알고리즘을 구현하겠습니다. 다음은 실제 구현 코드입니다:

func minMeetingRooms(_ meetings: [[Int]]) -> Int {
    guard meetings.count > 0 else {
        return 0
    }
    
    var startTimes = meetings.map { $0[0] }
    var endTimes = meetings.map { $0[1] }
    
    startTimes.sort()
    endTimes.sort()
    
    var roomCount = 0
    var endPointer = 0
    
    for startTime in startTimes {
        if startTime < endTimes[endPointer] {
            roomCount += 1
        } else {
            endPointer += 1
        }
    }
    
    return roomCount
}

코드 설명

위의 코드는 입력으로 받은 회의 시간 배열에서 각 회의의 시작 및 종료 시간을 분리하여 정렬합니다. 이 후 두 포인터를 사용하여 회의의 시작 시간과 종료 시간을 비교하면서 필요한 회의실의 수를 계산합니다.

guard 구문을 통해 회의가 없는 경우 0을 반환합니다.
회의의 시작 및 종료 시간을 각각 추출하고, 정렬합니다.
첫 번째 포인터는 매 회의를 반복하면서 시작 시간을 확인하고, 두 번째 포인터는 종료 시간을 추적합니다.
만약 시작 시간이 종료 시간보다 이른 경우, 새로운 회의실이 필요하므로 roomCount를 증가시킵니다.
모든 회의가 처리된 후 필요한 회의실의 수를 반환합니다.

복잡도 분석

이 알고리즘은 다음과 같은 복잡도를 가집니다:

시간 복잡도: O(n log n) – 시작 및 종료 시간을 정렬하는 데 O(n log n)의 시간이 소요됩니다.
공간 복잡도: O(n) – 추가적인 공간을 사용하여 회의 시작 및 종료 시간을 저장합니다.

결론

회의실 배정 문제는 여러 회의가 겹치지 않도록 관리하는 중요한 문제입니다. 주어진 알고리즘을 통해 회의실 사용의 효율성을 높일 수 있으며, 코딩테스트에서 자주 출제되는 문제 중 하나입니다. 스위프트로 문제를 해결하는 방법을 이해하고, 실제 코드를 구현해 보면서 연습하면 좋습니다.

추가 연습 문제

경우에 따라 종료 시간이 동일한 회의가 있을 때 처리 방법을 결정해 보세요.
회의 시간을 랜덤하게 생성해 주어진 회의 수에 따라 회의실 배정을 테스트 해 보세요.

이 게시물이 여러분에게 도움이 되기를 바랍니다. 이 문제를 통해 알고리즘 문제 해결 능력을 더욱 향상시키시길 바랍니다!