[백준] 강의실 배정 : 11000 : Java - 그리디

1. 💎  문제

11000번: 강의실 배정

 

 

 

 2. 🤔 접근

구해야 하는 것은 최소 강의실의 수이다. 그러므로 n개의 강의실을 운영하다가 n개의 강의실이 모두 꽉 차있어 새로운 강의를 열 수 없을 때, 강의실을 늘려준다. 

 

1. 우선 순위 큐 사용

n개의 강의실을 운영하기 위해 우선 순위 큐를 사용한다. 왜냐하면 최소의 강의실을 유지하기 위해서는 여러 개의 강의실 중 가장 일찍 끝나는 강의실에 새로운 강의를 배정해야 되기 때문이다. 그러므로 항상 가장 일찍 끝나는 강의실을 찾기 위해 삽입 시 오름차순 정렬을 해주는 우선 순위 큐를 사용한다.

 

2. 시작 하는 시간을 기준으로 오름차순 정렬

우선 N개의 강의를 시작하는 시간 기준으로 오름차순 정렬해야한다. 최소의 강의실을 사용하기 위해서는 비어있는 시간을 최소화해야 하기 때문이다. 또한 우선 순위 큐에는 강의가 끝나는 시간만 삽입하며, 요소 1개는 강의실을 나타낸다.

	// 시작 시간을 기준으로 오름차순 정렬
        Collections.sort(classes, ((o1, o2) -> {
            // 시작 시간이 같다면 끝나는 시간이 적은 것이 우선
            if(o1.start == o2.start)
                return o1.end - o2.end;
            return o1.start - o2.start;
        }));

 

3. n개의 강의 배치

우선 순위 큐에서 가장 첫 번째 요소(강의실)를 꺼내어 끝나는 시간과 현재 강의의 시작하는 시간을 비교한다. 만약 현재 강의의 시작 시간이 더 크거나 같다면 해당 강의실에서 강의를 하면 되어 강의실을 늘릴 필요가 없다. 하지만 현재 강의의 시작 시간이 더 작은 경우 해당 강의실에서 시작할 수 없으므로 새로운 강의실을 연다. 이때 첫 번째 요소(강의실)만 비교하는 이유는, 가장 빠르게 끝나는 강의실이기 때문이다.  

 	PriorityQueue<Integer> rooms = new PriorityQueue<>();
        rooms.offer(classes.get(0).end);

        for(int i=1; i<N; i++){
            Class cur = classes.get(i);
            if(rooms.peek() <= cur.start){
                // 가장 빠르게 끝나는 강의실에서 강의 시작 -> 끝나는 시간 갱신
                rooms.poll();
            }
            // 가장 빠르게 끝나는 강의실 보다 해당 강의의 시작 시간이 작으면 -> 새로운 강의실 배정
            rooms.offer(cur.end);
        }

 

+ TreeSet과 우선 순위 큐

처음 문제를 풀 때, 우선 순위 큐를 생각하지 못하고 TreeSet을 사용하였다. 분명 로직이 맞는 것 같은데 틀려서 꽤나 고민했는데 그 이유는 바로 TreeSet은 중복을 허용하지 않기 때문이었다! 그래서 중복 값이 들어오면 해당 값이 배제 되어서 오답이었던 것이다.

TreeSet과 우선 순위 큐는 삽입 시 정렬되는 자료구조이지만, 차이는 중복 허용 유무이다. TreeSet은 중복을 허용하지 않고, 우선 순위 큐는 중복을 허용한다.

 

 

 3. 🔆 코드

import java.io.*;
import java.util.*;

public class Main{

    public static BufferedReader br;
    public static BufferedWriter bw;


    public static void main(String [] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // N개의 수업
        int N = Integer.parseInt(br.readLine());
        List<Class> classes = new ArrayList<>();

        StringTokenizer st;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            classes.add(new Class(start, end));
        }
        // 시작 시간을 기준으로 오름차순 정렬
        Collections.sort(classes, ((o1, o2) -> {
            // 시작 시간이 같다면 끝나는 시간이 적은 것이 우선
            if(o1.start == o2.start)
                return o1.end - o2.end;
            return o1.start - o2.start;
        }));

        int count = 1;
        // 매번 가장 작은 요소를 찾아야 하기 때문에 TreeSet선택
        PriorityQueue<Integer> rooms = new PriorityQueue<>();
        rooms.offer(classes.get(0).end);

        for(int i=1; i<N; i++){
            Class cur = classes.get(i);
            if(rooms.peek() <= cur.start){
                // 가장 빠르게 끝나는 강의실에서 강의 시작 -> 끝나는 시간 갱신
                rooms.poll();
            }
            // 가장 빠르게 끝나는 강의실 보다 해당 강의의 시작 시간이 작으면 -> 새로운 강의실 배정
            rooms.offer(cur.end);
        }
        bw.write(rooms.size()+"\n");
        bw.flush();
    }

}

class Class{
    int start;
    int end;
    public Class(int start, int end){
        this.start = start;
        this.end = end;
    }
}