[BOJ 11000] 강의실 배정(Python)
문제
문제 해설
이 문제는 그리디 알고리즘을 이용해, 가장 수업 시간이 빠른 것들을 선택하는 문제입니다. N이 <= 200000 이므로 최대 NlogN 안에 들어오는 시간 복잡도를 가져야 시간 초과가 나지 않습니다.
정렬 카테고리에서 찾은 문제지만 고작 input을 sort()를 이용해 정렬한다고 해서 정렬로 분류될 문제인가 싶기도 합니다..
-
수업 정보를 리스트에 담습니다.
-
리스트를 정렬합니다. (가장 수업 시간이 빠른 것들을 선택하기 위함)
-
하나씩 꺼내서 우선순위 큐와 비교합니다. 우선순위 큐에는 수업이 끝나는 시간만 넣어줍니다. (가장 빨리 끝나는 강의와 비교하기 위함)
-
우선순위 큐를 pop합니다. (가장 빨리 끝나는 강의 시간)
-
현재 선택한 수업의 시작시간이 우선순위 큐의 TOP보다 작을 때(모든 강의실에 현재 수업을 넣을 수 없음), 새로운 강의실을 하나 만들어야 합니다. 우선순위 큐에 현재 수업을 새로 넣어줍니다.
-
현재 선택한 수업의 시작시간이 우선순위 큐의 TOP과 같거나 클 때(선택한 강의실에 현재 수업을 넣을 수 있음), 강의실에 현재 수업을 이어 붙입니다. 우선순위 큐에 현재 수업이 끝나는 시간을 새로 갱신시킵니다.
-
우선순위 큐의 크기를 리턴합니다.
풀이 코드
import sys
import heapq
input = sys.stdin.readline
pq = []
course = []
for _ in range(int(input())):
# 수업 정보를 리스트에 담아
course.append(list(map(int, input().split())))
course.sort()
heapq.heappush(pq, course[0][1])
for start, fin in course[1:]:
# 강의 시작 시간만 확인한다.
# pq pop한 것이 모든 강의실 중 가장 강의가 빨리 끝나는 시간이므로 이것만 확인한다.
first_fin = heapq.heappop(pq)
# 이어갈 수 있는 강의실이 없을때 강의실 하나 만든다.
if first_fin > start:
heapq.heappush(pq, fin)
# 현 강의실 중 붙여 넣을 강의실이 존재할 때
else:
first_fin = fin
first_fin = heapq.heappush(pq, first_fin)
print(len(pq))
Author And Source
이 문제에 관하여([BOJ 11000] 강의실 배정(Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qweadzs/BOJ-11000-강의실-배정Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)