[Python Algorithm] 강의실 배정 BOJ #11000

문제

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

11000번: 강의실 배정

 

내 문제 풀이

import sys
import heapq

n = int(sys.stdin.readline().strip())
times = [] # 입력되는 강의 시간들을 튜플 형태로 저장
rooms = [] # 각 원소가 하나의 강의실을 뜻하는 배열
for _ in range(n):
    (start, end) = map(int, sys.stdin.readline().strip().split())
    times.append((start, end))
times.sort(key=lambda x: (x[0], x[1])) # 시작 시간을 기준으로 오름차순 정렬, 시작시간이 같을 경우 종료 시간 기준 오름차순 정렬

for i in times:
    (start, end) = i
    if rooms and rooms[0] <= start:
        heapq.heappop(rooms) # rooms의 최솟값 pop
    heapq.heappush(rooms, end) # rooms에 현재 강의의 종료 시간 push

print(len(rooms))

👉 우선순위 큐 문제

• times 리스트에 강의 시간들을 튜플 형태로 받고, 시작시간을 기준으로 오름차순 정렬해주었다.
• rooms는 각 원소가 하나의 강의실을 뜻하는 배열인데, 강의실마다 끝나는 시간을 업데이트해주기 위해 만들었다.
• for문에서는 rooms 리스트가 비어있지 않고, 현재 강의의 시작 시간이 rooms의 최솟값보다 작을 경우
  rooms의 최솟값을 뺀 후 현재 강의의 종료 시간을 push할 수 있게 했다.
  => 최솟값이 들어있던 강의실의 종료 시간을 새롭게 업데이트해주는 부분이다.
• 위와 반대 경우에는 새로운 강의실이 필요한 것이므로, 그냥 현재 강의 종료 시간을 push하는 동작만 해주었다.
• rooms는 총 사용된 강의실들을 가지므로, 그 길이를 결과로 출력해주었다.

 

💡 피드백

• heapq를 처음써봐서 오래걸렸는데 이론도 같이 공부해봐야겠다.