[Python/파이썬] 백준 1374번 강의실

https://www.acmicpc.net/problem/1374

코드

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

n = int(input())
lectures = []
for _ in range(n):
    _, start, end = map(int, input().split())
    lectures.append((start, end))

lectures.sort()

needs = []
for i in range(n):
    start, end = lectures[i]
    if needs and needs[0] <= start:
        heappop(needs)
    heappush(needs, end)
print(len(needs))

 

이 문제는 heap 자료구조를 잘 알고 사용하는 것이 중요한 문제였다.

1. 강의 정보 정렬

  1-1. 각 강의의 시작 시간과 종료 시간만을 lectures 배열에 저장한다. 강의실 번호는 풀이 과정에 불필요하기에 저장하지 않았다.

  1-2. 강의들을 시작 시간 기준으로 정렬하고, 시작 시간이 같다면 종료 시간 기준으로 정렬한다

 

2. 최소 힙을 이용한 강의실 배정

needs 최소 힙은 현재 사용 중인 강의실들의 종료 시간을 저장한다. needs의 가장 앞에는 종료가 가장 빠른 강의실이 오게 된다.

정렬된 강의들을 순차적으로 처리하면서

  a. 현재 강의 시작 전에 끝나는 강의실이 있다면 (즉, needs의 최소값 ≤ 현재 강의 시작 시간), 해당 강의실을 재사용한다.

  b. 현재 강의의 종료 시간을 needs에 추가한다.

 

최종적으로는 needs의 크기가 필요한 강의실의 최소 개수가 된다.