[백준]_11000번 : 강의실 배정(파이썬)

11000번: 강의실 배정

 

우리의 목표는 강의 시작 시간과 끝 시간을 고려하여 최소 사용 강의실 수를 구하자 이다.

 

예를 들어 강의 시간을 다음과 같이 나타낸다면,

시간은 왼쪽에서 오른쪽으로 흐른다고 가정

(1, 2, 4) (3) 으로 총 2개의 강의실이 필요함을 알 수 있다. 물론 이 결과는 직관적으로 강의의 끝과 시작이 겹치는 1, 2, 4번 강의를 묶는 것이 강의와 강의 사이의 시간 낭비(공강)를 줄일 수 있기 때문에 나온 것이다.

 

즉 tuple(시작 시간(s), 끝 시간(f))이 원소인 리스트를 정렬하여 시작 시간과 끝 시간을 더 쉽게 관찰할 수 있게 해주는 것이 우선 같아 보인다.

 

예를 들어 정렬된 시간표 : (1, 8) (2, 4) (4, 9) (9, 10)  (9, 11) (11, 12)가 있다고 가정하자.

 

여기서 취할 수 있는 전략은 두 가지가 있다.

 

1. 처음부터 끝까지 돌며 이어지는 강의들을 이어 주기

 

예를 들어 (1, 8)을 pivot이라 했을 때 그다음 pivot은 (9, 10)이 될 수 있다. 왜냐하면 (현 pivot의 f) <= (9(s)).

 

두 번째 이후에 남은 강의 시간이 없기 때문에 반복문을 읽은 횟수가 결국 정답이 된다(위의 경우 2). 강의 시간들을 최대한 밀집되게 모아주겠지만 문제가 하나 존재한다.

 

시간 복잡도

 

pivot이 되어 주었던 시간표들을 다음 연산에서 제거해 주었다고 해도 최악의 경우

$N+(N-1)+(N-2)+ \cdots  +1=O(N^2) $의 시간 복잡도를 가질 수 있다. $N$이 20만까지 커질 수 있기 때문에 최악의 경우 400억 번의 연산을 해야 한다. 반드시 시간초과의 위험이 존재한다는 뜻이다.

 

2. 애초에 처음부터 강의실을 한꺼번에 배정해 주기

 

앞선 예시에서는 (2, 4)를 pivot의 8보다 2가 앞서기 때문에 무시했는데, 무시하는 대신에 새로운 강의실 배정을 해주는 것이다. 즉 pivot이 여러 개가 될 수 있다는 뜻인데, 이것을 전부 어떻게 관리할까? 

 

우리의 목적을 다시 떠올려 보자. 공강 시간을 최대한 줄이는 강의 시간을 선택하면 된다. 예를 들어 현재 검사하고자 하는 시간표가 (4, 5)이고 pivot(엄연히 말하면 강의실들의 가장 마지막 수업 시간들)들이 현재 [3, 7]이라고 하면, (4, 5)는 3이 마지막 시간인 강의실로 들어가면 되는 것이고 그와 동시에 더 이상 3은 그 강의실의 마지막 시간이 아니기 때문에 pop 해주고 5를 push 해준다.

 

반대로 시간표가 (4, 5)이고 pivot 리스트가 [6, 7] 이라면 (4, 5)가 이미 배정된 두 강의실 중에서 들어갈 수 있는 강의실은 없는 것이다. 그래서 새로운 강의실을 할당해주어야 하는데, (4, 5)의 f인 5를 [6, 7]로 push 하는 것이다.

 

위의 두 예시에서 보았듯이 pivot 리스트는 언제든지 원소들 중에서 가장 빠른 강의실 종료 시간(=리스트에서 가장 작은 값)을 반환할 준비가 되어 있어야 한다. 그래야지 차곡차곡 강의 시간들이 밀도 있게 쌓일 것이기 때문이다. 

 

이를 가장 잘 수행해주는 것이 바로 우선순위 큐이다.

순서도

 

pivots가 초기에 0을 갖고 있는 이유는 첫 번째 시간표를 반드시 포함시키게끔 하기 위해서이다. 

 

시간 복잡도

 

전체 데이터를 도는데 $O(N)$, push가 매번 일어날 때 힙 정렬 $O(N\log N)$이 소요되기 때문에 최종적으로 $O(N\log N)$ 의 시간 복잡도를 갖는다.   

 

최종 코드>>

import sys

input = sys.stdin.readline
import heapq

size = int(input())
timetable = []
for _ in range(size):
    s, f = map(int, input().split())
    timetable.append((s, f))
timetable.sort()
ls = [0]
for piv_s, piv_f in timetable:
    if piv_s >= ls[0]:
        heapq.heappop(ls)
    heapq.heappush(ls, piv_f)

print(len(ls))