[알고리즘] 백준 11000 - 강의실 배정

문제본문

문제 해설

가능한 빨리 시작하는 강의를 우선으로 진행하고, 시작하는 시간이 같다면 끝나는 시간이 빠른 강의들을 우선적으로 강의실을 배정합니다. 위의 기준으로 입력으로 들어오는 배열을 정렬합니다.

//O(nlong)
 Arrays.sort(room, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int result = o1[0] - o2[0];
                if (result != 0) return result;
                else return o1[1] - o2[1];
            }
        });

첫번째 강의가 3시에 끝나고, 두 번째 강의가 3시에 시작한다면 강의실을 새로 배정하지 않고 기존 강의실에서 수업을 진행할 수 있습니다. 따라서 정렬된 배열에 대해 순차적으로 지난 강의의 끝나는 시간과 수업이 시작되어야 하는 강의 시작시간을 비교하여 새롭게 강의실을 배정해야 하는 지 판단합니다.

그런데 배정중인 강의실이 1개가 아니라면 어떻게 판단해야 할까요? 저는 강의실의 끝나는 시간을 저장하는 리스트를 만들어 반목문을 돌면서 가장 끝나는 시간이 작은 강의를 찾아냈습니다. 이는 O(n)의 시간복잡도를 가집니다. 그런데 현재 바깥에서 강의실을 배정하는 반목문이 돌고 있기 때문에 총 O(n^2)이 되므로 시간초과가 발생합니다.

이러한 문제는 힙 자료구조인 PriorityQueue를 사용하여 해결할 수 있습니다. 데이터를 추가할떄 마다 내부적으로 힙 정렬을 통해 가장 작은 값이 0 인덱스로 오게 됩니다. 따라서 O(1)로도 판단이 가능합니다.

 

전체 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[][] room = new int[n][2];

        for (int i = 0; i < n; i++) {
            room[i][0] = scanner.nextInt();
            room[i][1] = scanner.nextInt();
        }
        //O(nlogn)
        Arrays.sort(room, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int result = o1[0] - o2[0];
                if (result != 0) return result;
                else return o1[1] - o2[1];
            }
        });

        //O(logn)
        PriorityQueue<Integer> roomSize = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {

            if (!roomSize.isEmpty() && roomSize.peek() <= room[i][0]){
                roomSize.poll();
            }
            roomSize.add(room[i][1]);
        }

        System.out.println(roomSize.size());
    }
}

 

참고

• 탐욕적 기법 - Ries