[백준] 11000 강의실

11000번: 강의실 배정 (acmicpc.net)

11000번: 강의실 배정

 

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

 

 

내 풀이

처음에는 이전에 그리디 알고리즘을 공부하며 풀었던 한 강의실에 최대한 많은 강의를 배정하는 문제와 유사하다고 생각하여, 최대한 많은 강의를 배정하는 것을 반복하며 배정하는 횟수를 세면 그것이 강의실의 갯수라는 논리를 생각했다.

즉,

1. 강의실을 최대한 많이 배정함 ( 강의가 끝나는 시간 순으로 Greedy 하게 선택)

2. 1번을 하면서 선택한 강의를 체크해두고 처음으로 선택하지 못한 강의를 기억해둠 (다음 탐색의 낭비를 줄이기 위해)

3.  1-2 번이 끝나면 한 강의실에 강의를 배정하는 것이 끝난 것임, 기억해둔 위치에서 다시 1-2번을 반복하며 다음 강의실에 강의를 배정한다

 

이런 방법으로 구현해보았지만 

줄인다고 했지만 결국에는 체크 배열 검사와 강의실 배정에 O(N^2) 가 되어 시간 초과가 나는게 아닐까라는 생각이 들었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static String src = "3\n" +
            "2 4\n" +
            "1 3\n" +
            "3 5";

    static int N, time, next, result;
    static int[][] data;
    static boolean[] checked;

    public static void main(String arg[]) throws IOException {
        input= new BufferedReader(new InputStreamReader(System.in));
        //input = new BufferedReader(new StringReader(src));

        StringTokenizer str;
        N = Integer.parseInt(input.readLine());

        data = new int[N][2];
        checked = new boolean[N];

        for (int i = 0; i < N; i++) {
            str = new StringTokenizer(input.readLine());
            data[i][0] = Integer.parseInt(str.nextToken());
            data[i][1] = Integer.parseInt(str.nextToken());
        }

        //끝나는 시간 기점으로 정렬함
        Arrays.sort(data, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                } else {
                    return o1[1] - o2[1];
                }
            }
        });

       /* for (int i = 0; i < N; i++) {
            System.out.println(Arrays.toString(data[i]));
        }*/

        result = 0;
        while (!isAllChecked()) {
            select(time);
            result++;
        }
        System.out.println(result);
    }

    public static void select(int start) {
        int time = start;

        //선택할 때 아닌 것의 첫번째 부터 확인함
        for (int i = next; i < N; i++) {
            //시작 시간이 강의 시작 시간보다 같거나 작고 배정하지 않은 강의인 경우
            if (time <= data[i][0] && !checked[i]) {
                //System.out.println(i +" " +time);
                checked[i] = true; //배정 체크
                time = data[i][1]; //시간 강의 끝난 시간으로 옮겨줌
            }
        }

    }

    //전부 배정하면 true 반환 아니면 false
    public static boolean isAllChecked() {
        for (int i = next; i < N; i++) {
            if (!checked[i]) { //아닌 경우의 첫번째
                time = data[i][0]; //시작 시간과
                next = i; //인덱스를 담아둠
                return false;
            }
        }
        return true;
    }

}

 

위와 같이 처음에 생각한 방법에서 틀리고 다른 방법을 생각하다가 다른 분들은 어떻게 풀었을까 를 찾아보고 해결하였다. 

[PS] 백준 #11000 강의실 배정 문제 풀이 (velog.io)

[PS] 백준 #11000 강의실 배정 문제 풀이

 

이분은 C++로 구현하셨는데 위에 설명하신 로직이 깔끔해서 이해될 때까지 읽어보고 구현해보니 깔끔하게 성공했다.

2개의 우선순위 큐로 구현하는데

우선 강의 우선순위 큐는 말 그대로 강의의 시작시간, 끝 시간을 갖고 강의의 시작이 빠른 순, 같다면 종료시간이 빠른 순으로 정렬하고, 강의실 우선순위 큐는 요소 하나가 각 강의실을 나타낼 것이고 강의실에서 진행된 마지막 강의의 종료시간을 담을 것이며 가장 종료시간이 빠른 순(작은 순)으로 정렬할 것이다.

이 상태에서 강의 큐에서 강의를 하나씩 꺼내 기존의 강의실에 넣을 수 있으면 (강의실의 가장 빠른 종료시간이 강의 시작 시간보다 더 빠른 경우) 강의실을 꺼내 강의의 종료시간으로 갱신해주고, 넣을 수 없다면 강의의 종료시간을 강의실 큐에 넣음으로서 새 강의실을 배정하는 작업을 반복한다. 

그 결과 강의실 큐의 크기가 바로 강의들을 배정하는데 사용한 강의실의 갯수가 되는 것이다.

 

내가 강의를 선별적으로 넣기 위해 탐색하느라 낭비한 O(N)을 이 알고리즘은 우선순위 큐로 빼주어 O(N logN)으로 구현한 모습이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static String src = "4\n" +
            "2 4\n" +
            "1 3\n" +
            "1 2\n" +
            "3 5";

    static int N;
    static boolean[] checked;

    public static void main(String arg[]) throws IOException {
        //input= new BufferedReader(new InputStreamReader(System.in));
        input = new BufferedReader(new StringReader(src));

        StringTokenizer str;
        N = Integer.parseInt(input.readLine());

        PriorityQueue<Lecture> priorityQueue = new PriorityQueue<>(); //수업 우선순위큐
        PriorityQueue<Integer> classQueue = new PriorityQueue<>(); //강의실 우선순위큐, 종료시간이 들어갈 예정
        checked = new boolean[N];

        for (int i = 0; i < N; i++) {
            str = new StringTokenizer(input.readLine());
            priorityQueue.add(new Lecture(Integer.parseInt(str.nextToken()), Integer.parseInt(str.nextToken())));
        }


        while (!priorityQueue.isEmpty()) { //수업 전부 배정할 때까지
            Lecture lecture = priorityQueue.poll();
            //강의는 시작이 빠른 순으로 정렬된 상태
            //강의실 우선순위큐가 종료시간을 담고, 작은 순으로 정렬됨
            if (classQueue.isEmpty()) { //강의실을 하나도 배정하지 않았다면 
                classQueue.add(lecture.endTime); 
            }else{
                //강의실의 가장 빠른 종료시간이 강의 시작시간보다 더 앞인 경우
                if(lecture.startTime >= classQueue.peek()) {  
                    //강의실의 가장 빠른 종료시간 꺼내고 강의의 종료시간으로 다시 넣음으로서 갱신함
                    classQueue.poll();
                    classQueue.add(lecture.endTime);
                } 
                //기존의 강의실에 넣지 못하는 경우 
                else {
                    //강의의 끝나는 시간을 강의실큐에 넣음으로서 새 강의실 배정
                    classQueue.add(lecture.endTime);
                }
            }
        }
        //고로 강의실 큐의 사이즈가 강의실 갯수
        System.out.println(classQueue.size());
    }

    static class Lecture implements Comparable<Lecture>{
        public int startTime;
        public int endTime;

        public Lecture(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }

        //시작시간 오름차순, 같은 경우 끝나는 시간이 빠른 순
        @Override
        public int compareTo(Lecture o) {
            if (this.startTime == o.startTime) {
                return this.endTime - o.endTime;
            } else {
                return this.startTime - o.startTime;
            }
        }
    }

}