* 백준 11000번 - 강의실 배정

Gyuhan Park·2021년 12월 2일
0

코딩테스트 정복

목록 보기
33/47

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. 최소 강의실 개수를 구하시오.

# 틀린 코드

이전에 풀었던 회의실 배정과 비슷한 맥락이라고 생각했다. 다른 점은 필요없는 강의를 pop()하지 않고 저장해야 한다는 점이다.

강의가 끝나는 시간 기준으로 정렬하면 한 강의실에서 최대 개수의 강의를 진행하므로 최소 강의실을 사용한다고 생각했다. 그래서 이중 for문을 돌렸는데 시간초과가 났다. 반복문 1개로 된다고?

시간이 안맞는 강의는 별도의 강의실에서 진행하고 새로운 강의는 어느 강의실에서 이어서 진행될지 확인하기 위해 2중으로 돌렸다. 이런 경우 보통 잘 정렬한 후 아이디어를 찾아 반복문 1개로 만드는 방법이 존재한다. 하지만 찾지 못했다. 뭐가 문제지?

import sys

input = sys.stdin.readline

N = int(input())
times = []
visited = []

for _ in range(N):
  s, t = map(int, input().split())
  times.append((s, t))

times.sort(key=lambda x:x[1])

visited.append(times[0])
for i in range(1, N):
  for j in range(len(visited)):
    if times[i][0] >= visited[j][1]:
      visited[j] = times[i]
      break
    if j == len(visited) - 1:
      visited.append(times[i])

print(len(visited))

# 참고 코드

핵심은 시작시간 기준 오름차순 정렬우선순위큐였다.
끝나는 시간 기준으로 하면 반복문 1번으로 해결할 수 없을 뿐만 아니라 최대 강의 개수와 최소 강의실 개수의 카운트 기준이 달랐다.
끝나는 시간과 시작시간의 간격이 최소가 되도록 하려면 시작시간 기준 오름차순 정렬이 필요하다.

우선순위큐는 python에서 heapq로 구현할 수 있다. 내가 반복문으로 해결하려 했던 문제를 heapq를 통해 O(N)에서 O(logN)으로 최적화가 가능하다. python에서 heapq는 min heap으로 구현되어 있다. 따라서 사용하고 있는 강의실에 끝나는 시간을 heap에 넣으면 빨리 끝나는 강의가 root 자리에 존재할 것이다.

즉, 가장 빨리 끝나는 강의보다 다음 강의가 더 일찍 시작하면 새로운 강의실에서 진행한다.

import heapq
import sys

input = sys.stdin.readline
N = int(input())

timeTable = [list(map(int, input().split())) for _ in range(N)]
timeTable.sort(key=lambda x: x[0])

queue = []
heapq.heappush(queue,timeTable[0][1])

for i in range(1,N):
    if queue[0] > timeTable[i][0]: # 진행중인 강의 중 가장 빠른 강의가 끝나기 전에 다음 강의가 있을 때
        heapq.heappush(queue,timeTable[i][1])
    else: # 이전 수업 뒤에 그 강의실에서 다음 수업을 진행할 수 있을 때
        heapq.heappop(queue)
        heapq.heappush(queue,timeTable[i][1])

print(len(queue))
profile
단단한 프론트엔드 개발자가 되고 싶은

0개의 댓글