백준 11000 강의실 배정 (Java,자바)

jonghyukLee·2022년 7월 3일

이번에 풀어본 문제는
백준 11000번 강의실 배정 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Lecture
{
    int start,end;

    public Lecture(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        Queue<Lecture> lectures = new PriorityQueue<>(new Comparator<Lecture>() {
            @Override
            public int compare(Lecture o1, Lecture o2) {
                if(o1.start == o2.start) {
                    return o1.end - o2.end;
                }
                return o1.start - o2.start;
            }
        });
        Queue<Integer> cur = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            lectures.add(new Lecture(start,end));
        }

        //첫 수업
        cur.add(lectures.poll().end);

        while (!lectures.isEmpty()) {
            //다음 강의 시작시간
            Lecture next = lectures.poll();

            if (next.start >= cur.peek()) {
                cur.poll();
            }
            cur.add(next.end);
        }

        System.out.print(cur.size());
    }
}

📝 풀이

N개의 강의의 시작시간, 끝나는 시간이 입력으로 주어질 때 필요한 강의실의 갯수를 출력하는 문제입니다.
강의의 시작 시간과 이전 강의가 끝나는 시간을 비교해야 하기 때문에 입력값에 대한 정렬이 필요했고, 정렬된 값에 따라 순서대로 강의를 진행해야 했기 때문에 우선순위 큐를 선택했습니다.
강의 시작 시간으로 정렬된 lectures 큐와, 강의가 끝나는 시간만 담은 cur 큐 두개를 활용합니다.
lectures에서 다음으로 진행될 강의를 꺼내고, cur 큐의 가장 최상단 값이 가장 먼저 끝나는 강의가 되므로 해당 값과 비교를 해줍니다. 만약 cur 큐의 값이 다음 강의가 시작될 시간보다 작거나 같다면, 해당 강의가 끝난 이후에 동일한 강의실을 사용하면 되므로 큐에서 꺼내줍니다. 당연히 반대의 경우는 빈 강의실이 없다는 의미 이므로 cur 큐에 다음 진행할 강의를 담아, 강의실을 추가해주게 됩니다.
위와 같은 작업을 반복했을 때, 모든 반복이 끝나고 남은 cur 큐의 크기가 필요한 강의실의 수가 됩니다.