[백준] 11000 - 강의실 배정 🏫 (Python) / 골드 5 / 정렬

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

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

문제

첫째 줄에 수업의 개수 N이 주어집니다. 다음으로 N줄에 걸쳐, 각 수업의 시작시간 Si와 끝시간 Ti가 공백을 구분자로 주어집니다. 모든 수업을 가능하게 하는 최소한의 강의실 개수를 출력해야합니다.

1) 예제 입출력❄️

예제 입출력

강의 1 3과 3 5는 끝시간과 시작시간이 같으니 한 교실에서 할 수 있지만, 2 4는 겹치기 때문에 다른 교실에서 해야합니다. 즉, 최소로 교실 2개가 필요하므로, 2를 출력합니다.

2. 핵심 논리☢️

[시작 시간, 끝 시간] 을 원소로 갖는 이중리스트에 대해 오름차순으로 정렬하고, 최소 힙에 끝시간을 저장하고, 시작시간이 끝시간과 겹치는 경우만 heap에 새로 추가하고, 겹치지 않으면, 끝시간을 갱신해가는 논리가 핵심입니다.

3. 풀이 코드✅

from heapq import heappush, heappop
import sys
input=sys.stdin.readline
N=int(input())
schooltime = sorted(list(map(int,input().split())) for _ in range(N))
heap = [schooltime[0][1]]
for s,t in schooltime[1:]:
    if heap[0] <= s:
        heappop(heap)
    heappush(heap,t)
print(len(heap))

schooltime에 [시작 시간, 끝 시간]을 원소로 갖는 이중리스트가 입력으로 들어옵니다. 이를 오름차순으로 정렬합니다. 이렇게 되면 시작시간이 빠른 순으로 정렬되고, 시작시간이 같으면 끝시간이 빠른순으로 정렬됩니다. 첫번째 수업의 끝시간으로 heap을 초기화 해줍니다. schooltime[1:]을 이용해 2번째 원소부터 s,t로 for문을 반복합니다. heap은 최소힙이며, heap[0]은 heap에서 최소값을 보장합니다. 즉, heap의 끝나는 시간 최소값(heap[0])과 s(시작 시간)을 비교해서 s(시작 시간)이 끝나는 시간(heap[0]) 이상이면, 최소값을 갱신해야 하므로, heappop을 하고 t로 heappush를 해줍니다. 만약 s(시작 시간)이 끝나는 시간(heap[0]) 이하라면, 수업 시간은 겹치게되고, heappush로 끝나는 시간을 추가만 해줍니다. 결과적으로 heap에는 최소한의 강의실 개수에 대해 끝나는 시간으로 채워져있어서, 길이를 출력하면 최소한의 강의실 개수를 출력합니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/5ba24331cd288dacb67fac27227e38dbdac74a99/jupyter/11000_%EA%B0%95%EC%9D%98%EC%8B%A4_%EB%B0%B0%EC%A0%95.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/