[BOJ] 백준 11000 강의실 배정 - Python/Java

문제

11000번: 강의실 배정

해설

그리디(Greedy)하게 풀 수 있는 간단한 문제이지만 약간의 고민해야 할 부분이 있는 문제라고 생각합니다.

 

기본적으로 이 문제는 '어떤 강의실을 차지하고 있는 수업이 끝나면, 해당 강의실을 재사용할 수 있다'는 점을 생각해야 하는데요. 이를 바탕으로 시작 시간이 빠른 수업을 먼저 강의실에 배정하는 전략을 세울 수 있습니다. 그렇게 하면 수업의 시작 시간과 사용 중인 강의실의 종료 시간을 비교해서 종료 시간보다 크거나 같은 수업은 강의실을 추가로 사용하지 않을 수 있기 때문이죠.

 

하지만 이렇게 그리디한 선택을 하기 위해서는 가장 빨리 끝나는 강의실에 대한 정보 역시 따로 저장하고 있어야만 합니다. 그래서 이를 위한 우선순위 큐를 하나 생성해야 하죠.

 

이 문제를 틀리게 되는 가장 큰 이유는 강의실의 사용 종료 시간을 변수 하나로 처리하려는 시도에서 오게 됩니다. 아래 코드가 틀린 코드입니다.

import sys
input = sys.stdin.readline

n = int(input())
lectures = [tuple(map(int, input().split())) for _ in range(n)]
lectures.sort(key = lambda x : (-x[0],x[1])) # 시작 시간이 빠른 강의부터 뽑기 위해 역순으로 정렬

answer = 1
start, finish = lectures.pop()
while lectures:
    s, f = lectures.pop()
    if s < finish: answer += 1
    else: finish = f
print(answer)

이렇게 하면 강의실을 재사용 할 수 있을 때만 강의실의 종료 시간을 갱신해주게 되는데요. 그러면 아래와 같은 반례가 생기게 됩니다.

 

[1] -------------------

[2] -------------

[3] ------

[4]          -----------

 

위와 같이 네 개의 수업이 존재한다고 해보겠습니다. 위의 수업들은 정렬된 상태입니다. 그러면 1 ~ 3번째 수업은 각각 다른 강의실을 이용해야 하고 이 상황에서 가장 먼저 끝나는 수업은 세 번째 수업입니다. 그러면 네 번째 수업은 세 번째 수업이 끝나는 순간 그 강의실을 이어서 사용하게 되죠. 그러면 현재 상황에서 가장 먼저 끝나는 강의실은 어떤 강의실이 될까요? 

 

바로 두 번째 강의실입니다. 하지만 위의 코드를 따라가보면, 네 번째 수업의 종료 시간이 가장 먼저 끝나는 강의실로 설정되게 되죠.

 

따라서, 올바른 코드는 아래와 같이 강의실의 종료 시간을 전부 따로 관리하는 방법입니다.

 

풀이 - 파이썬

import sys, heapq
input = sys.stdin.readline

n = int(input())
lectures = [tuple(map(int, input().split())) for _ in range(n)]
lectures.sort(key = lambda x : -x[0]) # 시작 시간이 빠른 강의부터 뽑기 위해 역순으로 정렬
start, finish = lectures.pop() # 맨 처음 강의를 하나 넣고 시작
endTime = [finish]
answer = 1
while lectures:
    finish = endTime[0]
    s, f = lectures.pop()
    if s < finish: answer += 1
    else: heapq.heappop(endTime)
    # 강의의 끝나는 시간을 항상 우선순위 큐에 삽입
    heapq.heappush(endTime, f)

print(answer)

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class B_11000 {
    static PriorityQueue<Integer> endTime = new PriorityQueue<>();
    static int n;
    static List<Lecture> lectureList = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        for(int i = 0 ; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int f = Integer.parseInt(st.nextToken());
            lectureList.add(new Lecture(s, f));
        }
        // 강의의 시작 순서를 기준으로 정렬
        lectureList.sort(Comparator.comparingInt(l -> l.start));
        endTime.add(lectureList.get(0).finish); // 맨 처음 강의를 하나 넣고 시작
        int answer = 1;
        for(int i = 1; i < lectureList.size(); i++){
            Lecture lec = lectureList.get(i);
            int finish = endTime.peek();
            if(lec.start < finish) answer++;
            else endTime.poll();
            // 강의의 끝나는 시간을 항상 우선순위 큐에 삽입
            endTime.add(lec.finish);
        }
        System.out.println(answer);
    }

    static class Lecture{
        int start, finish;
        public Lecture(int start, int finish){
            this.start = start;
            this.finish = finish;
        }
    }
}