[Baekjoon] 11000번: 강의실 배정

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정

문제 설명

그리디 문제이다. S에 시작해서 T로 끝나는 N개의 수업이 주어진다. 이때 최소의 강의실을 사용해서 모든 수업을 할 수 있게 해야 한다. 참고로 4시에 끝나면 4시에 시작하는 수업을 바로 시작할 수 있다. 즉, T_i <= S_j 일 경우 i 수업과 j 수업은 둘 다 한 강의실에서 할 수 있다.

풀이 방법

처음에는 끝나는 시간인 T로 오름차순 정렬한 후 다음 수업의 시작하는 시간과 비교해서 다음 수업 시작 시간이 작다면 강의실을 추가하는 식으로 문제를 해결하려 했다. 그러나 제출했을 때 틀렸다고 나왔고 인터넷에서 반례 글을 찾다가 그 이유를 알게 되었다. 반례는 다음과 같다.

4
1 2
1 4
2 6
4 5

이를 끝나는 시간으로 오름차순 정렬 후 계산하게 되면

1 2 --> 1
1 4 --> 2
4 5 --> 2
2 6 --> 3

으로 정렬되고 이를 알고리즘에 돌리면 결과는 3이 나온다. 이를 해결하려면 '시작하는 시간'을 기준으로 오름차순 정렬해야 한다. 그리고 힙 또는 우선순위 큐와 같은 자료구조를 이용하여 끝나는 시간을 오름차순으로 입력한다. 시작 시간을 기준으로 정렬하면 다음과 같다.

1 2
1 4
2 6
4 5

그리고 나서 끝나는 시간을 다른 오름차순 정렬이 되는 자료구조에 넣어 놓은 후 그 맨 처음이 다음 수업의 시작 시간과 비교해서 크거나 같다면 이어지는 것으로 간주하고 큐에서 뺀다. 그리고 다음 수업의 끝나는 시간을 큐에 넣어 놓는다. 이를 위 입력으로 생각해보면 다음과 같다.

q = []
1 2 --> 2 추가, [2]
1 4 --> 4 추가, [2, 4]
2 6 --> 2 빠지고 6 추가, [4, 6]
4 5 --> 4 빠지고 5 추가, [5, 6]

이렇게 되고 나면 큐에 마지막에 남는 개수만큼이 정답이 된다. 왜냐하면 연결되어 있는 수업은 모두 연산 과정에서 빠졌기 때문에 마지막에는 연결된 수업들의 마지막 수업이 끝나는 시간만 남아있기 때문이다.

전체 코드는 다음과 같다.

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

class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[][] lessons = new int[N][2];
        
        for (int i = 0; i < N; i++) {
            String[] split = br.readLine().split(" ");
            int S = Integer.parseInt(split[0]);
            int T = Integer.parseInt(split[1]);
            
            lessons[i][0] = S; lessons[i][1] = T;
        }
        
        Arrays.sort(lessons, (o1, o2) -> o1[0] - o2[0]);
        
        PriorityQueue<Integer> q = new PriorityQueue<>();
        
        for (int[] lesson : lessons) {
            if (!q.isEmpty() && q.peek() <= lesson[0]) {
                q.poll();
            }
            q.offer(lesson[1]);
        }
        
        System.out.print(q.size());
    }
}

회고

그리디나 구현, 시뮬레이션 문제는 BFS나 DFS처럼 해결 방법이 특정 알고리즘에 국한된 것이 아니라서 처음 떠오른 해결 방법으로 해결되지 않았을 때가 정말 고역인 것 같다. 이것도 결국 많은 문제를 풀어보면서 경험을 쌓아야 해결되는 거라고 생각하므로 더 많은 문제를 접해봐야겠다.