[백준 - Python] 11000. 강의실 배정 (그리디)

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

11000번: 강의실 배정

 

코드

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

n = int(input())
cl = []
for i in range(n):
    cl.append(tuple(map(int, sys.stdin.readline().split())))
cl.sort()

# 수업 시작 시간이 어떤 수업의 종료시간보다 같거나 늦으면 그 수업의 강의실에서 이어서 수업이 가능하다는 점
heap = [cl[0][1]] # 시작 시간이 가장 빠른 수업의 끝나는 시간
for s, t in cl[1:]:
    if heap[0] <= s:
        heappop(heap)
    heappush(heap, t)
print(len(heap))

 

N개의 수업을 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

강의실 개수의 최솟값을 구하는 문제였다.

 

회의실 배정 문제와 유사한 문제겠거니 했는데,

heapq를 활용해서 다르게 접근해야 하는 문제였다.

 

수업 시작 시간이 가장 빠른 수업의 끝나는 시간을 힙에 저장하고

이후의 정렬된 수업 리스트를 돌면서 탐색을 한다.

 

heap에 삽입을 하면 최소힙을 유지함으로

heap에서 0번째 인덱스는 무조건 가장 작은 값이 유지된다.

 

시작 시간이 힙에 저장된 끝나는 시간보다 같거나 늦으면,

이어서 수업이 가능하므로 heappop 후 해당 수업의 끝나는 시간을 heappush 해준다.

 

시작 시간이 힙에 저장된 끝나는 시간들 중 가장 빠르게 끝나는 시간보다도 빠르면,

heapq의 다른 수업들 이후로는 당연히 수업이 불가능하기 때문에

강의실을 추가로 개설해 주어야 한다.

따라서 heappush를 해준다.

 

heap에 저장된 요소의 개수가 개설된 최소 회의실의 개수이다.

 

정리

알고리즘은 결국 메모리 위에서 작동하는 것이기 때문에 자료구조를 벗어날 수 없다.

따라서, 알고리즘 문제는 자료구조를 기반으로 생각해야 한다.

 

유연하게 자료구조를 활용할 수 있는 능력이 중요해지는데,

그렇다면 사용 가능한 자료구조는 무엇이 있는지,

그리고 각 자료구조의 특징과 활용 방안은 어떻게 되는지

잘 알아두어야 할 것 같다.