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

프로그래밍 면접 준비를 하는 과정에서, 특정 알고리즘 문제를 해결하는 것은 매우 중요합니다. 오늘은 ‘회의실 배정하기’라는 주제로 자바로 문제를 해결해보겠습니다. 이 문제는 알고리즘과 자료구조를 이해하는 데 도움을 주며, 특정 조건을 만족하는 최적의 해답을 찾는 데 초점을 맞추고 있습니다.

문제 설명

다양한 회의들이 특정 시간 간격에 발생합니다. 각 회의는 시작 시간과 끝 시간을 가집니다. 목표는 모든 회의를 가능한 최소한의 회의실에서 할당하는 것입니다.

문제 정의

제목: 회의실 배정하기

입력:
- 여러 개의 회의가 주어질 때, 각 회의는 시작 시간과 끝 시간으로 정의됨 (start, end).
- 회의는 [[start1, end1], [start2, end2], ...] 형태로 주어짐.

출력:
- 회의실의 개수를 최소화하여 회의실을 배정했을 때 필요한 회의실의 수를 반환하시오.

예제 입력 및 출력

입력: [[0, 30], [5, 10], [15, 20]]
출력: 2  (회의실 2개 필요)

입력: [[7, 10], [2, 4]]
출력: 1  (회의실 1개 필요)

해결 접근법

이 문제를 해결하기 위해, 우리는 회의의 시작 시간을 기준으로 정렬하고, 우선순위 큐를 사용하여 현재 사용 중인 회의실의 종료 시간을 관리할 수 있습니다. 그 후, 각 회의를 순차적으로 확인하면서 새로운 회의실을 추가할지 여부를 결정합니다.

알고리즘 단계

회의를 시작 시간을 기준으로 오름차순으로 정렬합니다.
우선순위 큐를 사용하여 회의실의 종료 시간을 관리합니다.
각 회의를 확인하면서 종료 시간이 가장 빠른 회의실에 회의를 추가하거나 새로운 회의실을 할당합니다.
최종적으로 사용한 회의실의 개수를 반환합니다.

자바 코드 구현

아래는 위의 접근법을 바탕으로 구현한 자바 코드입니다:


import java.util.Arrays;
import java.util.PriorityQueue;

public class MeetingRooms {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) {
            return 0;
        }

        // 회의를 시작 시간을 기준으로 정렬합니다.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // 우선순위 큐를 사용하여 회의실의 종료 시간을 관리합니다.
        PriorityQueue minHeap = new PriorityQueue<>();

        for (int[] interval : intervals) {
            // 현재 회의의 시작 시간과 가장 빠른 회의실의 종료 시간을 비교
            if (!minHeap.isEmpty() && interval[0] >= minHeap.peek()) {
                minHeap.poll(); // 회의실을 해제
            }
            // 새 회의실이 필요하다면 종료 시간 추가
            minHeap.add(interval[1]);
        }

        // 사용된 회의실의 수 반환
        return minHeap.size();
    }

    public static void main(String[] args) {
        MeetingRooms meetingRooms = new MeetingRooms();
        int[][] intervals = {{0, 30}, {5, 10}, {15, 20}};
        System.out.println("필요한 회의실의 수: " + meetingRooms.minMeetingRooms(intervals));

        int[][] intervals2 = {{7, 10}, {2, 4}};
        System.out.println("필요한 회의실의 수: " + meetingRooms.minMeetingRooms(intervals2));
    }
}

결과 및 시간 복잡도

위의 코드를 실행하면 주어진 회의에 필요한 회의실의 수를 정확히 계산할 수 있습니다. 이 알고리즘의 시간 복잡도는 다음과 같습니다:

회의를 정렬하는 데 O(n log n)의 시간이 걸립니다.
각 회의를 확인하면서 우선순위 큐에 추가하거나 제거하는 데 O(n log k)의 시간이 걸립니다.

그 결과, 전체 시간 복잡도는 O(n log n + n log k)로 분석할 수 있습니다. 여기서 n은 회의의 수, k는 사용 중인 회의실의 개수입니다.

마무리

이번 글에서는 ‘회의실 배정하기’ 문제를 해결하기 위한 접근법과 자바 코드 구현을 자세히 살펴보았습니다. 코딩 테스트 준비에 많은 도움이 되었기를 바라며, 자료구조와 알고리즘을 통해 문제 풀이 능력을 더욱 강화하시기 바랍니다.