[백준] 11000번 강의실 배정

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q11000.kt

최소한의 강의실로 모든 강의를 들을 수 있도록 하여라.
강의실의 수업이 끝나자마자 바로 다음 강의를 시작할 수 있다.

처음 생각

이전에 풀어본 [백준] 1931번 회의실배정 보다 살짝 어려워졌다. 접근은 비슷한 방식으로 진행하지만 처리를 해주어야하는 부분에 있어서 고민을 조금 하였다.

▶ 회의실 배정처럼 한 개의 방이아닌 다양한 방을 처리해 주어야하므로 일찍 끝나는 회의실을 우선적으로 처리를 해주었고, 끝나는 시간이 같을 경우에는 시작 시간이 빠른 순서대로 처리를 해주었다.

다음 생각

하나의 방이 사용중이면 새로운 방을 늘려주어야한다. List를 가지고 구현을 하려다가 PriorityQueue(우선 순위 큐)가 생각이나서 PriorityQueue를 사용하였다.(물론 방의 순서가 앞서 이야기한 순서대로 넣어주어야 한다.)

▶ 방의 끝나는 시간만 가지고 있으면 되므로 Integer 타입으로 선언 해주었다.

▶ PriorityQueue를 사용한 이유는 끝나는 시간이 빠른 순서대로 방을 교체해 주기 위해서다.

다다음 생각

PrioirtyQueue의 가장 우선순위의 끝나는 시간과 새로 비교해야할 강의의 시작시간을 비교해서 기존 강의를 끝내고 새로운 강의를 시작해 줄지, 기존 강의가 아직 끝나지 않았으니 새로운 강의를 새로 넣어줄 지를 결정한다. 새로운 강의가 들어가도 PriorityQueue이기 때문에 끝나는 시간이 빠른 강의가 우선 순위로 채택된다.

다다다음 생각

모든 비교를 마치고 PriorityQueue에 남아있는 자료의 양이 필요한 강의실의 수가 된다.

방안

1) Kotlin 풀이(Java 풀이와 비교해서 코드가 짧긴하나 Kotlin 컴파일러를 거쳐서 실행되서 그런가 살짝 더 느린감이 있었다.)

package baekjoon.q10000
 
import java.util.*
import kotlin.Comparator
 
fun main(args:Array<String>){
    var sc : Scanner = Scanner(System.`in`)
    var n = sc.nextInt()
    var arr : Array<Pair> = Array(n,{Pair(0,0) })
    for(i in 0..(n-1))
        arr[i] = Pair(sc.nextInt(),sc.nextInt())
 
    Arrays.sort(arr, Comparator { o1: Pair, o2: Pair ->
        if(o1.e==o2.e) o1.s.compareTo(o2.s)
        else o1.e.compareTo(o2.e) })
    var result = 1
    var end = arr[0].e
    for(i in 1..(n-1)){
        if(arr[i].s>=end){
            result++
            end = arr[i].e
        }
    }
    println(result)
}
class Pair(val s: Int, val e: Int)

2) Java 풀이

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Pair[] arr = new Pair[n];
        for(int i=0;i<n;i++)
            arr[i] = new Pair(sc.nextInt(),sc.nextInt());
        Arrays.sort(arr,Pair.comparator);
        pq.add(arr[0].e);
        for(int i=1;i<n;i++){
            // 새로운 시작시간이 pq의 빨리끝나는 시간보다 같거나 크다면 기존 강의실 이용
            if(pq.peek()<=arr[i].s) pq.poll();
            pq.add(arr[i].e);
        }
        System.out.println(pq.size());
    }
 
    static class Pair{
        int s,e;
        Pair(int s,int e){
            this.s = s;
            this.e = e;
        }
        static Comparator<Pair> comparator = new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                if(o1.s==o2.s) return Integer.compare(o1.e,o2.e);
                else return Integer.compare(o1.s,o2.s);
            }
        };
    }
}