[백준] 11000번 : 강의실 배정 (Java)

 

🔗 11000번 : 강의실 배정
● Java 풀이
● 시간 제한 1초
● 메모리 제한 256 MB

✅ 문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 
김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 
참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)
수강신청 대충한 게 찔리면, 선생님을 도와드리자!

---

✅ 테스트 케이스

/** 출처 (https://steady-coding.tistory.com/253) **/
// input
6
1 3
2 5
7 8
9 10
7 11
4 12

// answer
3

---

✅ 풀이

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

public class Main {
    private static class Lecture {
        public Lecture(long start, long end) {
            this.start = start;
            this.end = end;
        }

        long start, end;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());  // 강의 개수
        Lecture[] lectures = new Lecture[N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            // 강의 추가
            st = new StringTokenizer(br.readLine());
            lectures[i] = new Lecture(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
        }

        Arrays.sort(lectures, (o1, o2) -> {
            if (o1.start == o2.start) return Long.compare(o1.end, o2.end);
            return Long.compare(o1.start, o2.start);
        });  // 시작 시간이 빠른 순 (같다면 종료시간이 빠른 순)으로 오름차순 비교

        PriorityQueue<Long> pq = new PriorityQueue<>();  // 종료 시간을 정렬해 담을 Priority Queue
        pq.add(lectures[0].end);  // 첫 강의의 종료 시간 삽입

        for (int i = 1; i < N; i++) {
            if (pq.peek() <= lectures[i].start) {  // 종료 시간 이후 해당 강의가 시작될 경우
                pq.poll();  // pq 가장 앞의 강의 종료 시간을 해당 강의로 대체
            }
            pq.add(lectures[i].end);  // 강의 종료 시간 삽입
        }

        System.out.println(pq.size());  // 강의실 개수 출력
    }
}

 

브루트포스를 사용하면 시간 초과가 나는 문제. 

정렬을 사용한 그리디 알고리즘과 우선순위 큐를 사용하여 푸는 문제이다.

 

1-1) 강의를 입력 받은 후 시작 시간을 오름차순으로 정렬한다.

1-2) 시작 시간이 같다면 종료 시간을 오름차순으로 정렬한다.

2) 시작 시간이 가장 빠른 첫 번째 강의를 첫 번째 강의실에 배정한다. (Priority Queue에 삽입한다)

3) Priority Queue에는 종료시간을 삽입하므로, 탐색한 강의 중 가장 빠른 종료시간이 삽입된다.

4) 두 번째 강의부터 탐색하며 가장 빠른 종료 시간 (pq.poll())과 현재 강의의 시작 시간을 비교한다.

5-1) 시작 시간이 가장 빠른 종료 시간 이후일 경우 해당 강의실의 강의를 이 강의로 대체하기 위해 이전 강의 종료 시간을 제거하고, 현재 강의 종료시간을 Priotiry Queue에 삽입한다.

5-2) 시작 시간이 가장 빠른 종료 시간 이전일 경우 다른 강의실을 써야하므로, 현재 강의 종료 시간을 Priority Queue에 새로 삽입한다.

 

🤔 강의 시작 시간을 기준으로 정렬하는 이유

 

🔗  https://steady-coding.tistory.com/253

위 블로그에서 반례를 잘 들어주어, 참고하며 글을 작성해보려 한다.

시작 시간을 기준으로 정렬하는 이유는 그리디 알고리즘을 활용한 풀이 방식과 밀접한 관련이 있다.

 

그리디 알고리즘의 핵심은 현재 가장 최적의 답을 구하는 것으로, 현재 강의의 강의실을 찾는 경우에는 다른 강의에 대해선 신경 쓰지 않는다는 것이다.

다른 강의가 몇 시에 시작해 몇 시에 끝나는지 신경 쓰지 않고, 최대한 강의를 붙이고, 몰아넣기 위해서는 이전 강의 종료 후 잉여 시간이 없을 = 시작 시간이 빠른 강의를 삽입해야 한다는 것이다.

 

위 테스트 케이스로 함께 살펴보자.

종료 시간을 기준으로 정렬할 경우

 

{3} : Priority Queue에 (1, 3) 강의의 종료 시간인 3이  1 강의실에 먼저 삽입이 된다.

{3, 5} : 이후 (2, 5) 강의의 시작 시간 2와 가장 빠른 종료 시간 3을 비교했을 때 1 강의실에 삽입할 수 없으니, 2 강의실에 해당 강의를 삽입한다. 

{5, 8} : 종료시간 기준 정렬 시 (4, 12) 강의가 아닌 (7, 8) 강의가 다음 순서로 오게 된다. 7을 가장 빠른 강의 종료 시간 3과 비교했을 때, 강의가 다음 차례에 진행될 수 있으므로 3을 제거하고 7을 1 강의실에 삽입한다.

{8, 10} : 다음엔 (9, 10) 강의를 가장 빠른 종료 시간을 가진 2 강의실과 비교했을 때, 삽입할 수 있으므로 2 강의실의 종료 시간인 5를 제거하고, 10을 삽입한다.

(...생략)

 

과연 이 방식이 옳은 방식일까?

 

위와 같은 방식으로 진행하다 보면, 강의실이 비는 잉여시간이 너무나 많이 발생하게 된다.

앞서 언급했듯, 그리디 알고리즘을 사용하는 이유는 다음 강의를 신경쓰지 않고, 잉여시간을 최대한 없애 최적의 효율로 최소의 강의실을 쓰기 위해서이다. 

이를 위해서는 가장 빠른 시작 시간과, 가장 빠른 종료시간을 최대한 붙여야 한다는 의미이다. 이에 따라 시작 시간을 기준으로 정렬하는 것이 옳은 방식이라고 말할 수 있다.

 

시작 시간을 기준으로 정렬할 경우

시작 시간을 기준으로 정렬했을 경우엔, 종료 시간 기준 방식과 달리 강의실을 3개만 사용해도 된다는 것을 알 수 있다. 

현재 강의를 이전 강의와 비교하여 잉여 시간을 최소로 하여 배치함으로써 공간을 활용하는 그리디 방식을 사용한 것이다.

 

이와 비슷한 시간 배정 문제를 보게된다면 그리디 알고리즘과 Priority Queue를 사용한 방법을 떠올리는 것이 중요할 것 같다.