2 분 소요

[공지사항] 알고리즘 카테고리 포스트 살펴보기

:rocket: 문제 설명

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

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

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

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

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

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

강의실의 개수를 출력하라.




:rocket: 문제 풀이

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




public class Main {
    public static void main(String[] args) throws IOException {
        // 입력 받는 파트
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int classNum = Integer.parseInt(br.readLine());
        ArrayList<int[]> classList = new ArrayList<>();

        for (int i = 0; i < classNum; i++){
            st = new StringTokenizer(br.readLine());
            int[] classVar = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            classList.add(classVar);
        }

        Collections.sort(classList, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0])
                    return o1[1] - o2[1];
                return o1[0] - o2[0];
            }
        });

        // 풀이
        PriorityQueue<Integer> finishedTimePQ = new PriorityQueue<>();

        finishedTimePQ.add(classList.get(0)[1]);

        for (int i = 1; i < classNum; i++){
            if (finishedTimePQ.peek() <= classList.get(i)[0]){
                finishedTimePQ.poll();
            }
            finishedTimePQ.add(classList.get(i)[1]);
        }
        bw.write(Integer.toString(finishedTimePQ.size()));
        bw.flush();
    }
}

입력 받는 것은 이전에 풀었던 회의실 배정 문제랑 같다.

[회의실 배정 문제 풀이] 링크


다만 다른 부분은 거기서는 회의실을 하나로 고정하고 가능한 한 많은 회의 예약을 잡는 것이 문제였다면

여기서는 모든 강의를 다 잡으면서, 강의실 개수를 최소화하는 것이다.

언뜻보면 헷갈리지만 완전히 다르다. 다만 두 방식 모두 그리디 접근 방식을 사용한다.

이 문제에서는 그리디 뿐만 아니라 우선순위 큐도 사용한다.

백준 1931 회의실 배정과의 차이

회의실 배정과 마찬가지로 입력받은 강의를 정렬해야 한다.

근데 회의실 배정에서는 끝나는 시간을 기준으로 정렬했는데 여기서는 그래서는 안된다.

회의실 배정에서는 더 빨리 끝나는 회의를 먼저 잡아서, 한 회의실에 최대한 많은 회의를 우겨넣는 것이 관건이었다. 겹치는 회의는 버린다.

그러나 강의실 배정에서는 반드시 모든 강의를 다 진행해야 하기 때문에.

‘어 이 강의는 겹치네? 강의가 겹치면 강의실을 하나 더 잡아야지’로 판단한다.

이때, 무작정 하나를 더 잡는게 아니라, 강의실의 개수를 최소로 하기 위해 아직 확인하지 않은 강의 목록 중에 시작 시간이 빠른 걸 뽑아서

가장 빨리 끝나는 강의실의 강의 종료 시간이랑 비교를 해야 한다.

이것 때문에

  • 강의 목록 중 시작 시간이 빠른 걸 뽑기 위해, 시작 시간으로 강의 목록 리스트 (classList 변수)를 정렬하고,
  • 가장 빨리 끝나는 강의실을 뽑기 위해, 강의 종료 시간이 빠른 것을 먼저 꺼내주는 우선순위 큐를 쓴다.

:rocket: 문제 풀이

위 내용을 코드로 구현하는데 Priority Queue, 우선순위 큐가 적용된다.

우선순위 큐에 담기는 것은 각 강의실의 마지막 강의가 끝나는 시간이다.

가장 빠르게 수업이 끝나는 강의실(우선순위 큐에 peek()하면 구할 수 있다.)에 해당 강의를 시작해도 되는지 비교를 한 후에 시작할 수 없다면 강의실을 하나 더 잡아버리는 것이다.

다른 깅의실은 비교할 필요가 없다.

우선순위 큐에서 peek해서 확인한 강의실이 안되는데, 다른게 될리가 없다. 다른 강의실은 더 늦게 끝나기 때문이다.

만약 시작할 수 있다면 해당 기록을 poll()해서 빼버리고 현재 강의 종료 시간을 넣어준다.

우선순위 큐에 담긴 건 각 강의실의 마지막 강의의 종료 시간이다.

즉, 우선순위 큐의 사이즈를 출력해주면 강의실의 최소 개수가 된다.



:smile: 후기

문제 푸는 것도 헷갈리는데 설명하는게 더 헷갈리는 문제다…

내 어휘력의 한계를 느낀다.

참고