1. 오늘의 문제
처음 이 문제를 봤을 때 첫인상은 별로 어렵지 않아 보였다.
그런데 풀다 보니까 잘 안풀림.
예전에 쉽게 풀었던 유형은 강의실의 수가 정해져 있었는데 이번에는 최소의 강의실 수를 구하네...?
이번에도 못풀어서 검색을 통해 해결했다.
문제
N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.
물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다. 강의 시작 시간과 강의 종료 시간은 0 이상 10억 이하의 정수이고, 시작 시간은 종료 시간보다 작다.
2. 원리
1) 먼저 첫번째 수업의 끝나는 시간을 큐에 넣는다.
2) 다음 수업의 시작 시간이 끝나는 시간보다 큰지, 작은지를 확인한다.
3) 만약 수업의 시작 시간이 앞 수업의 끝나는 시간보다 작다면 큐에 끝나는 시간을 새롭게 추가한다.(강의실 추가)
4) 수업 시작 시간이 끝나는 시간보다 크다면 기존의 시간을 제거하고 다음 수업의 끝나는 시간을 큐에 넣는다.
5) 이때의 조건은 큐가 항상 정렬되어 있다는 것. 제거할 때 제거되는 첫번째 순위는 큐 내부에서 수업이 끝나는 시간이 가장 빠른 것부터이다. 이것을 우선순위 큐라고 한다. 우선순위 큐는 힙 정렬을 이용해 구현할 수 있다.
6) 이것을 반복한다.
7) 큐의 길이를 측정하고 반환한다.
3. 코드
from sys import stdin
import heapq
put = stdin.readline
numOfClass = int(put())
times = []
for _ in range(numOfClass):
number, startTime, endTime = map(int, put().split())
times.append([startTime, endTime])
times.sort()
rooms = []
heapq.heappush(rooms, times[0][1])
for i in range(1, numOfClass):
if times[i][0] < rooms[0]:
heapq.heappush(rooms, times[i][1])
else:
heapq.heappop(rooms)
heapq.heappush(rooms, times[i][1])
print(len(rooms))
4. 느낀점
내가 힙 정렬과 우선순위 큐를 모른다는 사실을 알게 되었다.
힙 정렬은 수업으로 한번 들었던 것인데, 이렇게 이용할 수 있을 거라고 생각하진 못했다.
처음에는 리스트 내부에서의 합을 이용하려고 했는데 범위가 너무 넓어서 시간 초과가 났다.
오늘 또 하루 배워가는 하루다.
