[백준] 11000 강의실 배정 - 자바

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

11000번: 강의실 배정

문제 풀이

이 문제를 해결하는데 참 많은 시간이 걸렸다.

우선 이전 백준1931번 회의실 배정 문제가 기억이 나서 종료시간을 기준으로 정렬하고 각 강의실마다 배치될 수 있는 것들을 묶어 이 세트의 개수를 세서 해결해봤다.

역시나 바로 1트 실패,,
틀린 코드는 굳이 보여주진 않겠지만 이중반복문으로 해당 문제가 원하는 시간복잡도에는 미치지 못했다.

그래서 다른 방법을 찾아서 해결했는데 그 방법은 각 종료시간을 기준(오름차순)으로 큐에 넣고 하나씩 빼면서 주어진 시작시간과 큐에 있는 종료시간과 비교하여 들을 수 있는 강의면 해당 종료시간이 저장된 큐를 하나씩 제거한다.
이때 제거가 되고 남은 큐의 개수가 총 강의실이 개수가 된다.

여기서 중요한 점은 종료시간을 기준으로 정렬하는 것이 아니라 시작시간으로 정렬해야한다

왜일까?
우선 작성한 로직상 해당 종료시간과 비교하여 가장 먼저 시작하는 강의 순서대로 차곡차곡 빼나가는 방법으로 작성되어있다. 사실 여러 글을 찾아보고 이해하려고 해봐도 글로 설명하기는 어려워서 반례를 겨우 찾았다.
왜 시작시간 기준으로 해야 하는지 이해가 안 간다면 직접 코드를 따라가보길 바란다.

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

코드는 다음과 같다.

코드

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

class lecture {
    int start;
    int end;
    public lecture(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        List<lecture> lectures = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            lectures.add(new lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        // start 기준으로 오름차순, start 같을 시 end 기준으로 오름차순 정렬
        Collections.sort(lectures, new Comparator<lecture>() {
            @Override
            public int compare(lecture o1, lecture o2) {
                if (o1.start == o2.start) {
                    return o1.end - o2.end;
                }
                return o1.start - o2.start;
            }
        });

        // 우선순위 큐에는 종료 시간만 들어가며, 오름차순으로 자동 정렬된다.
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(lectures.get(0).end);

        for (int i = 1; i < n; i++) {
            // 우선순위 큐에서 가장 작은 종료 시간과
            // 현재 lectures[i]의 시작 시간을 비교한다.
            if (pq.peek() <= lectures.get(i).start) {
                pq.poll();
            }
            pq.offer(lectures.get(i).end);
        }
        System.out.println(pq.size());
    }
}

또 알아두어야 할 것은 회의실 배정에 문제처럼 강의실을 가능한 많이 연결하는 로직에서 종료시간 기준으로 정렬하는 것이 틀렸다는 것이 아니다.

 

위 문제도 종료시간을 기준으로 이어붙일 수 있는 강의실을 계속 이어 나가며 만들어진 강의실의 세트를 세면 똑같은 결과를 만들 수 있다.
하지만 주어진 제약(시간복잡도)를 맞추기 위해 다른 로직을 이용했고 이 로직에서 필요한 값이 시작시간을 기준으로 정렬해야 한다는 의미이다.