🏆 알고리즘 문제 풀이
📌 문제 정보
- 문제명 : 강의실 배정
- 문제 번호 : 11000
- 출처 : https://www.acmicpc.net/problem/11000
- 난이도 : G4
- 유형 : 정렬 / 우선순위 큐(Priority Queue)
🧐 문제 설명
서로 다른 시간에 진행되는 여러 개의 강의가 있을 때,
모든 강의를 겹치지 않게 진행하기 위해 필요한 최소 강의실의 수를 구하는 문제이다.
각 강의는 시작 시간(start)과 종료 시간(end)이 주어진다.
한 강의가 끝나는 즉시 다음 강의가 시작될 수 있다.
같은 시간대에 겹치는 강의는 서로 다른 강의실에서 진행되어야 한다.
👉 출력 : 모든 강의를 배정하기 위해 필요한 최소 강의실 개수
💡 접근 방법
-
시작 시간이 빠른 순으로 강의 정렬
→ 순서대로 처리하면서 강의실 배정 가능 여부를 판단. -
현재 진행 중인 강의들의 종료 시간 관리
→ 가장 빨리 끝나는 강의의 종료 시간을 우선순위 큐(PriorityQueue) 로 관리 -
새로운 강의 배정 로직
- 새로운 강의의 시작 시간이 가장 빨리 끝나는 강의의 종료 시간보다 크거나 같으면, 해당 강의실을 재활용(poll) 가능
- 그렇지 않다면 새 강의실 추가(add) 필요
- 최종적으로 큐에 남은 원소의 개수 = 필요한 강의실 수
📝 문제 설계
✅ 변수 정의
| 변수명 | 설명 |
|---|---|
n | 전체 강의 개수 |
lectures[] | 강의 정보를 저장하는 배열 |
start, end | 각 강의의 시작/종료 시간 |
pq | 현재 진행 중인 강의들의 종료 시간을 관리하는 우선순위 큐 |
✅ 알고리즘 흐름
1️⃣ 강의 정보를 입력받아 Lecture 객체로 저장
2️⃣ 시작 시간 기준으로 오름차순 정렬
3️⃣ 우선순위 큐(pq)에 첫 강의의 종료 시간을 삽입
4️⃣ 나머지 강의들을 순회하면서
- 가장 빨리 끝나는 강의(
pq.peek())와 시작 시간 비교 - 재활용 가능하면
poll(), 아니면 새 강의실add()
5️⃣ 모든 강의 처리 후pq.size()출력
✅ 시간 복잡도
- 정렬: O(N log N)
- 각 강의에 대해 PQ 삽입/삭제: O(N log N)
→ 총합: O(N log N)
N ≤ 100,000이므로 충분히 빠름
💡 사용 자료구조
🧱 우선순위 큐(Priority Queue)
일반 큐는 먼저 들어온 데이터가 먼저 나가는 구조(FIFO)이다.
우선순위 큐는 들어온 순서가 아니라 값의 우선순위(크기 등)에 따라 먼저 나가는 구조
가장 우선순위가 높은(또는 작은) 값이 먼저 나오는 큐
예시
- 일반 큐: [3, 5, 2, 4] → 꺼내면 3 → 5 → 2 → 4 순
- 우선순위 큐(작은 값 우선): [3, 5, 2, 4] → 꺼내면 2 → 3 → 4 → 5 순
즉, 자동으로 정렬된 상태를 유지하면서 꺼내면 항상 “가장 작은” (또는 “가장 큰”) 값을 돌려주는 구조
구현
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(2);
pq.add(7);
System.out.println(pq.poll()); // 2 (가장 작은 값)
System.out.println(pq.poll()); // 5
System.out.println(pq.poll()); // 7
}
}add()oroffer()→ 값 넣기poll()→ 가장 우선순위 높은(기본은 가장 작은) 값 꺼내기peek()→ 꺼내지 않고 확인만 하기
🌐 만약 큰 값 우선으로 꺼내려면
PriorityQueue는 기본적으로 오름차순 (작은 값 먼저) 정렬
내림차순으로 바꾸려면 Comparator 사용
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());🌐 이 문제에서는?
강의의 종료 시간을 우선순위 큐에 넣어 → “가장 빨리 끝나는 강의실”을 먼저 확인 및 재활용
💡 사용 알고리즘
- 정렬 (Sort)
- 우선순위 큐 (Priority Queue)
📚 알고리즘 선택한 근거
- 강의 시작 시간을 기준으로 순차적으로 처리해야 하므로 정렬 필요
- 종료 시간이 가장 빠른 강의를 효율적으로 관리하기 위해 우선순위 큐 적합
- 단순 배열로는 매번 최소 종료 시간을 찾기 어려우므로 PQ가 시간 효율적이다.
입력 & 출력 예시
🧑💻 코드
package Baekjoon;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
public class B_11000_강의실배정 {
static int n, classCount;
//강의 객체
static class Lecture {
int start, end; //시작시간, 종료시간
Lecture(int s, int e) {
start = s;
end = e;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
Lecture[] lectures = new Lecture[n];
//강의정보입력
for (int i = 0; i < n; i++) {
int s = sc.nextInt();
int e = sc.nextInt();
lectures[i] = new Lecture(s, e);
}
// 1️. 시작 시간 기준으로 정렬
Arrays.sort(lectures, (a, b) -> a.start - b.start);
// 2️. 종료 시간 관리용 우선순위 큐 (가장 작은 end가 먼저)
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 3️. 첫 강의의 종료시간을 큐에 넣음
pq.add(lectures[0].end);
// 4️. 나머지 강의들 순회
for (int i = 1; i < n; i++) {
Lecture lec = lectures[i];
// 현재 가장 빨리 z끝나는 강의와 비교
if (pq.peek() <= lec.start) {
pq.poll(); // 강의실 재활용 가능 → 제거
}
pq.add(lec.end); // 새 종료시간 추가
}
// 5️. 큐에 남은 강의실 수 = 필요한 강의실 수
System.out.println(pq.size());
}
}🔍 코드 해설
1️⃣ Lecture 클래스
static class Lecture {
int start, end;
Lecture(int s, int e) {
start = s;
end = e;
}
}- 각 강의의 시작시간(
start), 종료시간(end)를 저장하는 단순한 데이터 구조 - 여러 강의를 정렬하거나 비교하기 위해 별도의 객체 형태로 저장
2️⃣ 정렬
Arrays.sort(lectures, (a, b) -> a.start - b.start);- 시작 시간이 빠른 순서대로 강의를 정렬하여 순차적으로 시간표를 배정할 수 있도록 함
3️⃣ 우선순위 큐 활용
PriorityQueue<Integer> pq = new PriorityQueue<>();- 각 강의실에서 현재 진행 중인 강의의 종료 시간만 저장
pq.peek()→ 가장 빨리 끝나는 강의 확인
4️⃣ 강의 배정 로직
if (pq.peek() <= lec.start) pq.poll();
pq.add(lec.end);- 현재 가장 빨리 끝나는 강의의 종료시간이 새로운 강의의 시작시간보다 작거나 같으면 → 같은 강의실 재사용
- 그렇지 않으면 → 새로운 강의실 추가
5️⃣ 결과
System.out.println(pq.size());- 현재 진행 중인 강의의 개수가 곧 필요한 강의실 수
- 모든 강의 배정이 끝난 후 pq에 남아 있는 개수 출력
