[Python 문제풀이] 백준 11000번: 강의실 배정

문제

백준 11000번: 강의실 배정 (골드 5)

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

11000번: 강의실 배정

 

---

풀이과정

(start_time, end_time)을 tuple형태로 리스트에 저장한 뒤 정렬한다는 것,

그리고 각각의 시간을 강의실 저장 배열의 원소들과 비교해야한다는 것까진 생각해냄.

 

하지만 강의실 저장 배열이 항상 정렬 상태를 유지하면 비교가 쉬워진다는 것을 생각해내지 못함.
==> 우선순위 큐, heapq 라이브러리 사용!

 

강의실 저장 배열의 첫번째 원소가 항상

가장 처음으로 끝나는 강의실 (end_time이 가장 빠른 강의실)을 저장해야 한다는 점을 생각해야 함.

 

그 뒤 수업 시간을 저장한 배열에서 시작시간와 끝나는 시간을 꺼내어 비교하면 됨.

 

비교하면서 필요한 pop과 push는 각각 heapq라이브러리의 heappush()와 heappop()을 사용하여

항상 첫번째 원소가 최소값이 되도록 설정해야함.

 

• 참고: heapq 라이브러리 사용법: https://5ji-record.tistory.com/144

[Python 자료구조] max-heap, min-heap과 heapq 모듈

 

---

제출한 코드

import sys
import heapq

# 정렬상태를 유지해야하므로 우선순위 큐 사용

input = sys.stdin.readline

n = int(input())
lecs = []
rooms = []

for _ in range(n):
    start, end = map(int, input().split())
    lecs.append((start, end))

lecs.sort()
rooms.append(lecs[0][1])

for (s, e) in lecs[1:]:
    if s < rooms[0]:
        heapq.heappush(rooms, e)
    else:
        heapq.heappop(rooms)
        heapq.heappush(rooms, e)

print(len(rooms))