C# 코딩테스트 강좌, 회의실 배정하기

이 강좌에서는 C#을 사용하여 회의실 배정 문제를 해결하는 방법을 단계별로 설명합니다. 회의실 배정 문제는 알고리즘적 사고를 증진시키며, 여러 코딩 테스트에서 자주 출제되는 주제이기도 합니다.

문제 정의

다음과 같이 회의의 시작시간과 종료시간이 주어집니다. 각 회의는 특정한 시작시간과 종료시간을 가지고 있으며, 회의는 동시에 진행될 수 없습니다. 주어진 모든 회의를 수용할 수 있는 최소한의 회의실 개수를 구하는 문제입니다.

입력

    첫 번째 줄에 회의의 개수 N이 주어집니다. (1 ≤ N ≤ 10⁵)
    다음 N개 줄에는 각각의 회의의 시작 시간 start와 종료 시간 end가 공백으로 구분되어 주어집니다. (0 ≤ start < end ≤ 10⁶)

출력

회의실의 개수를 출력합니다.

예제

문제 해결 접근 방법

이 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용할 수 있습니다:

우선 모든 회의의 시작시간과 종료시간을 기준으로 정렬합니다.
각 회의를 차례대로 확인하며, 현재 사용 중인 회의실의 종료시간과 비교하여 새로운 회의를 시작할 수 있는지 결정합니다.
새로운 회의가 시작될 수 있다면, 해당 회의실의 종료시간을 갱신하고, 그렇지 않다면 새로운 회의실을 사용할 준비를 합니다.
마지막으로 사용한 회의실의 개수를 반환합니다.

C# 코드 구현


using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static void Main() {
        int n = int.Parse(Console.ReadLine());
        List<(int start, int end)> meetings = new List<(int start, int end)>();

        for (int i = 0; i < n; i++) {
            var parts = Console.ReadLine().Split(' ');
            int start = int.Parse(parts[0]);
            int end = int.Parse(parts[1]);
            meetings.Add((start, end));
        }

        // 회의 시간을 종료 시간 기준으로 정렬
        meetings.Sort((a, b) => a.end.CompareTo(b.end));

        // 회의실 개수를 세기 위한 변수
        int roomCount = 0;
        PriorityQueue minHeap = new PriorityQueue(); // 우선순위 큐 사용

        foreach (var meeting in meetings) {
            // 현재 회의 시작 시간이 가장 먼저 끝나는 회의실의 종료시간보다 크거나 같으면
            if (minHeap.Count > 0 && minHeap.Peek() <= meeting.start) {
                minHeap.Dequeue(); // 회의실 재사용
            }
            // 새로운 회의실 사용
            minHeap.Enqueue(meeting.end, meeting.end);
        }

        roomCount = minHeap.Count; // 남아있는 회의실 수
        Console.WriteLine(roomCount);
    }
}

해설

위의 알고리즘은 대체로 그리디 알고리즘에 해당합니다. 각 회의를 경과하며 현재 종료되는 회의실을 체크하여 최소한의 회의실을 사용하도록 설정합니다. 우선순위 큐를 사용하여 현재 사용 중인 회의실들을 효율적으로 관리합니다. 이 알고리즘은 다음과 같은 절차로 통하여 최적의 결과를 도출합니다:

시간복잡도 분석

알고리즘의 주된 Time Complexity는 O(N log N)입니다. 이는 회의의 리스트를 정렬하는 데 소요되는 시간입니다. 이후 각 회의를 확인하는 과정은 O(N)에 해당하므로 총 시간복잡도는 O(N log N)이 됩니다.

공간복잡도 분석

공간복잡도는 O(N)입니다. 유지하는 리스트와 우선순위 큐에 회의 정보를 저장하기 때문입니다.

결론

이번 강좌에서는 C#을 이용한 회의실 배정 문제의 해결 방식을 살펴보았습니다. 이 문제를 풀며 그리디 알고리즘의 적절한 활용법과 우선순위 큐의 효율적인 사용법을 배울 수 있었습니다. 다양한 회의실 배정 문제가 있을 수 있으니 연습을 통해 더 많은 문제를 해결해보길 바랍니다.

문제 정의

입력

출력

예제

문제 해결 접근 방법

C# 코드 구현

해설

시간복잡도 분석

공간복잡도 분석

결론

관련