99클럽 코테 스터디 19일차 TIL / 그리디

✏️ 문제

[백준/BOJ] 1374번: 강의실(https://www.acmicpc.net/problem/1374)

 

N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.

물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 G5

✅ 소요 시간: 59분

✅ 권장 시간: 1시간 30분

 

💡 풀이

1) 문제 이해

백준 11000번: 강의실 배정 문제와 동일하다. 이 문제를 풀 때 '우선순위 큐' 개념과 '최소 힙' 개념을 알게 됐는데, 이 문제에서도 저 개념들이 쓰였다.

 

2) 아이디어 흐름

① 강의 시작 시간 기준으로 정렬

 

② 최소 힙 초기화

 

③ 강의 시간 리스트를 순회하면서 현재 강의 시작 시간이 가장 이른 종료 시간보다 크거나 같다면 강의실 재사용

 

④ 현재 강의 종료 시간을 힙에 추가

 

일단은 간략하게 적어두고 나중에 수정...!

 

3) 구현

import sys
import heapq

input = sys.stdin.readline

N = int(input())

lectures = []

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

lectures.sort()

# 최소 힙 초기화
rooms = []

for start, end in lectures:
    # 현재 강의 시작 시간이 가장 이른 종료 시간보다 크거나 같다면 강의실 재사용
    if rooms and rooms[0] <= start:
        heapq.heappop(rooms)
    
    # 현재 강의 종료 시간을 힙에 추가
    heapq.heappush(rooms, end)

print(len(rooms))

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 강의실 배정 문제와 똑같다는 것과 시작 시간 기준으로 정렬해야 한다는 걸 바로 떠올렸지만 우선순위 큐를 써야 하는 건 바로 떠올리지 못했다.

❗ 배운 점

• 우선순위 큐의 개념과 동작 방식에 대해 깊게 공부해볼 필요가 있다.