백준 11000 강의실 배정 (JAVA)

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

11000번: 강의실 배정

 

문제 설명

강의의 시작 시간과 끝나는 시간을 주어졌을 때 모든 강의를 할 수 있게 몇개의 강의실을 빌려야하는지를 계산하는 프로그램을 구현해야 합니다.

 

문제에 대한 아이디어

이 문제는 회의실 배정문제와 유사합니다.

그래서 처음에는 인풋값을 끝나는 시간을 기준으로 오름차순 정렬을 하고 우선순위 큐에 집어 넣으면서 만약 현재 우선순위 큐에 peek 값보다 시작하는 시간이 작다면 우선순위 큐에 넣어주는 형식으로 진행을 했습니다.

 예를 들어 1 3을 집어 넣으면 현재 우선순위 큐 peek는 (1 3)이고 그 다음 (2 4)를 생각해보면 2가 3보다 작으므로 우선순위 큐에 집어 넣습니다. 그 후 (3 5)는 peek값의 끝나는 값인 3 과 같으므로 (1 3)을 poll하고 (3 5)를 집어 넣습니다. 이런 식으로 하면 쉽게 문제를 풀 수 있을 것 같았지만 틀렸습니다.

 

에러 찾기

어디서 에러가 생기는지 찾기 위해 여러 반례값을 생각해봤습니다. 이 반례를 찾는게 코테에서 가장 어려운 문제인 것 같습니다. 위에 처럼 풀었을 때 문제 점은 우선순위 큐에서 poll할 때가 문제였습니다. 

8
1 8
9 16
3 7
8 10
10 14
5 6
6 11
11 12

이런 예제를 생각해봤을 때 위의 풀이 처럼 풀면 (5, 6), (3, 7), (1, 8)이 들어간뒤 (8, 10)을 검사할 때 (5, 6)이 빠지게 됩니다. 하지만 (1, 8)이 빠져야 강의실을 최소로 배정할 수 있습니다.

결국 우선순위 큐에 집어넣을 때는 시작 순서가 빠른 순서로 집어 넣고 우선 순위 큐 안에서는 끝 나는 순서가 빠른 순서로 정렬을 해야 한다는 것을 알았습니다. 

 

전체 코드

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

public class 백준_11000_강의실_배정 {
    public static class Time implements Comparable<Time>{
        int s,e;
        public Time(int s, int e){
            this.s = s;
            this.e = e;
        }
        public int compareTo(Time t){
            if(this.s == t.s) return this.e - t.e;
            else return this.s - t.s;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int n = Integer.parseInt(st.nextToken());
        ArrayList<Time> arr = new ArrayList<>();
        for(int i = 0; i < n; ++i){
            st = new StringTokenizer(buf.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr.add(new Time(s, e));
        }
		
        // 시작 순서가 빠른 순서로 정렬
        Collections.sort(arr);

		// 우선 순위 큐에서는 끝나는 순서가 빠른 순으로 정렬
        PriorityQueue<Time> pq = new PriorityQueue<>((c1, c2) -> {
            if(c1.e == c2.e) return c1.s - c2.s;
            else return c1.e - c2.e;
        });

        pq.add(arr.get(0));
        int answer = 1;
        for(int i = 1; i < n; ++i){
            Time now = pq.peek();
            if(now.e > arr.get(i).s) {
                ++answer;
                pq.add(arr.get(i));
            }
            else {
                pq.poll();
                pq.add(arr.get(i));
            }
        }
        System.out.println(answer);
    }
}

https://github.com/SeWooooong/CodingTest_Practice/tree/main/%EB%B0%B1%EC%A4%80/Gold/11000.%E2%80%85%EA%B0%95%EC%9D%98%EC%8B%A4%E2%80%85%EB%B0%B0%EC%A0%95