[백준 11000] 강의실 배정 Python

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

 

 

문제 풀이 전략

1. 문제 접근방식
   • 그리디 알고리즘 + 최소 힙을 활용
   • 강의를 시작하는 시간을 기준으로 정렬 후, 끝나는 시간과 다음 강의 시작 시간 비교
2. 핵심 아이어
   • 힙에는 현재 사용중인 강의실에 종료시간을 저장
   • 새 강의 시작 시간이 가장 빨리 끝나는 강의실의 종료 시간 이상이면 → 그 강의실 재사용
   • 그렇지 않으면 → 새 강의실 추가

 

해결 과정

1. 강의 정보(시작, 종료시간)를 리스트에 정렬 후 시작 시간 기준 정렬
2. 첫 번째 강의의 종료시간을 힙에 push
3. 두 번째 강의의부터 순회 :
   • 새 강의 시작시간 >= 힙의 최솟값 (heapqpop)
   • 새 강의 종료 시간 (heapqpush)

 

전체 코드

 

 

 

어려웠던 점 & 개선

삽질의 기록: "모든 방을 다 뒤져야 하나?" (시간 초과)

처음에는 단순하게 생각했습니다.

1. 강의를 시작 시간 순으로 정렬한다.
2. 새로운 강의가 들어올 때마다 기존에 만들어둔 모든 강의실을 하나씩 확인한다.
3. "빈 방 있나요?" 하고 물어보고 없으면 새 방을 만든다.

하지만 이 방식은 강의실 개수가 많아질수록 매번 모든 방을 스캔해야 해서 시간 복잡도가 O(N^2)까지 치솟습니다. N=200,000인 이 문제에서는 가차 없이 '시간 초과' 판정을 받게 되죠.

 

개선한 점 : "최소 힙(Min-Heap)으로 끝나는 시간만 관리하자!"

우리가 궁금한 건 "지금 당장 비는 강의실이 있는가?"이지, 모든 강의실의 상세 스케줄이 아닙니다.

1. 시작 시간 기준 정렬: 일단 강의들을 순서대로 배치합니다.
2. 최소 힙(Priority Queue) 사용: 현재 사용 중인 강의실들의 '종료 시간'만 힙에 넣습니다.
   • 힙의 맨 위(top)에는 가장 빨리 끝나는 강의실의 시간이 기록됩니다.
3. 그리디한 판단:
   • 새 강의의 시작 시간이 힙의 top(가장 빨리 끝나는 시간)보다 크거나 같다면? -> 방을 이어 쓸 수 있습니다! (기존 시간을 뺴고 새 종료 시간을 넣기)
   • 아니라면? -> 방이 더 필요합니다. (새 종료 시간을 힙에 추가)

이렇게 하면 매번 모든 방을 뒤질 필요 없이, 힙 덕분에 O(N \log N)만에 해결 가능합니다!

 

 

 

 

---

백준 골드 달성!!