BOJ 11000 강의실 배정

기

직전에 풀었던 회의실 배정 문제와 매우 흡사해서, 보자마자 같은 형식으로 코드를 작성했다. 아래는 해당 코드이다.

import sys
from collections import deque

n = int(input())
l = []
for _ in range(n):
    s,e = map(int, sys.stdin.readline().strip().split())
    l.append((s,e))
l = sorted(l, key = lambda x: x[0])
l = sorted(l, key = lambda x: x[1])
cnt = 0

while l:
    tmp = []
    start, end = l[0][0],l[0][1]
    tmp.append((start,end))
    for s,e in l[1:]:
        if s >= end:
            tmp.append((s,e))
            start,end = s,e
    for t in tmp:
        l.remove(t)
    if l:
        cnt += 1

print(cnt)

대차게 틀렸다. 시간 초과가 난다는 것인데.. 코드의 로직에서 시간복잡도를 크게 줄일 수는 없다고 판단했다. 더 효율적인 자료구졸르 선택해야 하는 것이다.

승

사실  이 문제는 학교에서 수행했던 과제와 거의 비슷한 문제이다. 그 때 풀었던 문제는 힙을 이용한 우선순위 큐 문제였는데, 그 때 과제의 시간복잡도 허용치가 널널했기에(...) 많은 학생들이 큐를 이용해서 쉽게 풀었다던 교수님의 말씀이 기억났다.

그렇다면 이제는 힙과 우선순위 큐를 이용해 제대로 풀어봐야 할 차례다.

우선순위 큐는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 이 때 힙을 이용해서 구현하는 것이 가장 효율적이다. 파이썬에는 heapq 모듈로 손쉽게 힙 구현이 가능하기에, 이번 문제를 푸는 데 사용해 보았다.

전

우선 회의실 배정 문제와 같이, 강의 시간을 오름차순으로 정리하였다.

강의들의 시작, 종료 시간이 담긴 큐와 별도의 우선 순위 큐를 만들었다. 그리고 강의 시간이 담긴 큐를 순회하면서 현재 강의실의 강의 종료 시간보다 시작 시간이 이른 강의는 새로운 강의실을 배정하였다. 현재 배정된 강의실에 들어갈 수 없는 강의를 발견하면 새로운 강의실을 편성하는 방식이다. 이 때, 새로운 강의실이 필요한 지에 대한 여부는 강의 종료 시간에만 영향을 받기 때문에, 우선 순위 큐에는 강의 종료 시간만을 push/pop 했다.

결

힙을 이용해보면서 인상 깊었던 점은, 최대/최소값의 push/pop이 정말 빠르다는 점과 push/pop 이후에 힙이 자동으로 정렬된 상태를 유지한다는 것이다. 자료구조 시간에 배웠을 때는 크게 와닿지 않았는데, 실제로 문제를 풀어보니 이런 스케쥴링 문제에 정말 적합한 자료구조라는 사실을 알게 됐다.

---

코드

import heapq
import sys

n = int(input())
q = []

for _ in range(n):
    s,e = map(int, sys.stdin.readline().strip().split())
    q.append((s,e))
q.sort()

h = []
heapq.heappush(h, q[0][1])

for i in range(1,n):
    if q[i][0] >= h[0]:
        heapq.heappop(h)
        heapq.heappush(h, q[i][1])
    else:
        heapq.heappush(h, q[i][1])

print(len(h))