[백준] 11000. 강의실 배정 (그리디/Java)

[백준] 11000. 강의실 배정

[백준] 1931. 회의실 배정

📌 풀이 과정

직전에 회의실 배정 문제를 풀어서 그런지, 강의실 배정 문제도 끝나는 시간 기준으로 정렬하고 풀었더니 시간초과가 났다.

// 내가 처음에 짠 코드 (시간초과)
PriorityQueue<Lecture> pq = new PriorityQueue<>((l1, l2) -> {
    if(l1.end == l2.end) return l1.start - l2.start;
    return l1.end - l2.end; // 끝나는 시간 순 정렬
});

while(true){
    count++;
    Lecture tmp = pq.poll();
    List<Lecture> remainLecture = new ArrayList<>();

    while(!pq.isEmpty()){
        Lecture next = pq.poll();
        if(tmp.end <= next.start){
            tmp = next;
        } else {
            remainLecture.add(next);
        }
    }

    if(!remainLecture.isEmpty()){
        pq.addAll(remainLecture); // 여기서 문제!
    } else break;
}

 

왜 시간초과가 났을까?

먼저 회의실 배정 문제와 차이점을 분석해봤다. 회의실 풀이 코드를 바탕으로 문제를 풀었기때문.

 

🤔 회의실 vs 강의실 배정 차이점

회의실 배정 (백준 1931번)

• 목표: 하나의 회의실에서 최대한 많은 회의 진행
• 핵심: 일부 회의만 선택해서 최대 개수 구하기
• 알고리즘: 끝나는 시간 순 정렬 → 그리디 선택

강의실 배정 (백준 11000번)

• 목표: 모든 강의를 다 진행하되 필요한 강의실 최소 개수 구하기
• 핵심: 모든 강의를 다 하되 최소 자원 구하기
• 알고리즘: 시작 시간 순 정렬 → 강의실 상태 관리

 

💡 시간초과 원인

내 코드는 회의실 배정 방식을 강의실 배정에 억지로 적용한 것이었음을.. 알았다 ㅋ

최악의 경우: O(N² log N)
- 강의실이 N개 필요한 경우
- 각 강의실마다 전체 강의를 다시 순회
- N번 × N개 = N² 연산

예를 들어 강의가 100개이고 강의실이 50개 필요하면 → 50번 × 100개 = 5000번 처리해야 한다.

 

회의실 배정 코드 (O(N log N))

// 끝나는 시간 순 정렬
PriorityQueue<Meeting> pq = new PriorityQueue<>((m1, m2) -> {
    if(m1.end == m2.end) return m1.start - m2.start;
    return m1.end - m2.end;
});

int answer = 1;
Meeting tmp = pq.poll();

while(!pq.isEmpty()){
    Meeting next = pq.poll();
    if(tmp.end <= next.start){
        answer++;
        tmp = next;
    }
}

강의실 배정 코드 (O(N log N))

// 시작 시간 순 정렬
PriorityQueue<Lecture> lectures = new PriorityQueue<>((l1, l2) -> l1.start - l2.start);

// 각 강의실의 끝나는 시간 관리
PriorityQueue<Integer> classrooms = new PriorityQueue<>();

while(!lectures.isEmpty()){
    Lecture cur = lectures.poll();

    // 가장 빨리 끝나는 강의실에 배정 가능한지 확인
    if(!classrooms.isEmpty() && classrooms.peek() <= cur.start){
        classrooms.poll(); // 기존 강의실 재사용
    }
    classrooms.offer(cur.end); // 현재 강의의 끝나는 시간 추가
}

System.out.println(classrooms.size());

 

✨ 제출 코드

메모리: 71092 KB

시간: 592 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{

	static class Lecture{
		int start;
		int end;

		public Lecture(int start, int end){
			this.start = start;
			this.end = end;
		}
	}

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

		// 수업 시작 시간 순으로 정렬
		PriorityQueue<Lecture> lectures = new PriorityQueue<>((l1, l2) -> l1.start - l2.start);

		for(int i = 0; i < N; i++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			lectures.add(new Lecture(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}

		PriorityQueue<Integer> classrooms = new PriorityQueue<>();

		while(!lectures.isEmpty()){
			Lecture cur = lectures.poll();

			// 가장 빨리 끝나는 강의실에 배정 가능한지 확인
			if(!classrooms.isEmpty() && classrooms.peek() <= cur.start){
				classrooms.poll();
			}

			// 현재 강의의 끝나는 시간을 강의실에 추가
			classrooms.offer(cur.end);
		}

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

	}
}