백준 : 1379 강의실2

백준 : 1379 강의실2

문제 요약

• 총 N개의 강의가 있다.
• 각 강의는 세 가지 정보:
  • 강의 번호
  • 시작 시간
  • 종료 시간
• 겹치는 강의들은 서로 다른 강의실이 필요하다.
• 목표:
  1. 최소 강의실 개수 출력
  2. 각 강의마다 배정된 강의실 번호 출력 (강의 번호 순)

문제 분석

이 문제는 전형적인 그리디 + 우선순위 큐 (heapq) 문제입니다.

📌 강의실 배정의 본질

• 겹치지 않는 강의들은 같은 강의실을 사용할 수 있다.
• 가장 먼저 끝나는 강의실부터 체크하면서 빈 방이 있으면 재사용.
• 없다면 새로 방을 배정한다.

📌 주의

• 강의 번호와 강의 순서는 다르다!
  • 출력은 강의 번호 순
  • 처리 순서는 시작 시간 순
• 따라서 입력을 받아서 → 시작 시간 기준으로 정렬 → 결과는 별도 배열에 저장

최종 코드

import sys, heapq
input = sys.stdin.readline

n = int(input())
lect = []
for _ in range(n):
    a, b, c = map(int, input().split())
    lect.append((a, b, c))

lect.sort(key=lambda x : (x[1], x[2], x[0]))
room = [0] * n
q = []
count = 0

for i, start, end in lect :
    if q and q[0][0] <= start:
        end_time, room_num = heapq.heappop(q)
    else :
        count += 1 
        room_num = count
    room[i-1] = room_num
    heapq.heappush(q, (end, room_num))
    # print(f"{q} cnt:{count}")

print(count)
for num in room:
    print(num)

1. 입력 받은 강의 리스트 정렬
   • 시작 시간 순으로 정렬
   • 시작 시간이 같은 강의는 종료 시간을 기준으로 정렬
   • 종료 시간이 같아면, 강의 번호 기준으로 정렬
   • lect.sort(key=lambda x : (x[1], x[2], x[0]))
2. 우선순위 큐 사용
   • 힙에는 (종료 시간, 강의실 번호) 형태로 저장
   • 현재 강의 시작 시간이 힙의 최소값 (가장 빨리 끝나는 강의) 보다 크면, 해당 방 사용 (pop 후 push)
3. 강의실 번호별로 강의실 번호 저장
   • 강의 번호 순서대로 출력하기 위해 별도 배열 사용 : room[ 강의번호 - 1 ]
4. 결과 출력
   • 총 강의실 개수와 강의 번호 순서대로, 배정한 강의실 번호 출력

백준 답과 강의실 지정 번호가 틀리더라도, 패스를 받을 수 있다.

큐 구현