[BOJ 11000] 강의실 배정 (Python)

kimdukbae·2021년 4월 29일
0

[BOJ 11000] 강의실 배정 (Python)



풀이

처음 '수업이 끝나는 시간'을 기준으로 오름차순 정렬을 한 뒤에 2중 for문을 사용하여 최적의 강의실을 구하는 방식으로 접근하였다. 하지만, 당연히 시간 초과가 발생하였다. N은 최대 200,000으로 N^2은 400억이다. N^2이 40,000,000으로 착각하여 가능한 풀이라고 생각하였다...

문제의 포인트는 '수업 시작 시간'을 기준으로 오름차순 정렬을 하는 것과 우선순위 큐를 활용하는 것이다. 우선순위 큐에 있는 원소 각각 하나는 하나의 강의실에서 하나의 수업을 진행 중이라고 생각하면 된다. 이러한 포인트를 통해 시간 복잡도를 낮춰 문제를 풀 수 있게 된다.

왜 '수업 시작 시간'을 기준으로 오름차순 정렬을 해야하는지 궁금할 수 있다. 이는 반례를 통해 알아보자.

(Ex)
4
1 2
1 4
2 6
4 5

'시작 시간' 기준으로 오름차순 정렬 후에 답을 구하면 2이라는 답이 나온다.

'시작 시간' 기준으로 오름차순 정렬하여 답을 구한 경우
수업 목록 : (1 2) (1 4) (2 6) (4 5)
(1 2) -> (2 6)
(1 4) -> (4 5)
으로 정답은 2다.


이번엔 '끝나는 시간' 기준으로 오름차순 정렬 후에 답을 구해보자.

'끝나는 시간' 기준으로 오름차순 정렬하여 답을 구한 경우
수업 목록 : (1 2) (1 4) (4 5) (2 6)
먼저 수업 목록의 순서부터 달라지게 된다!
(1 2) -> (4 5)
(1 4)
(2 6)
으로 정답은 3이 나오게 된다.

이러한 반례를 통해 '시작 시간'을 기준으로 오름차순 정렬해야하는 것을 알 수 있다.


그리고 우선순위 큐에는 '수업 끝나는 시간'만 큐에 삽입해야 한다. 즉, (수업 시작 시간, 수업 끝나는 시간)의 형태로 '수업 시작 시간'도 같이 삽입하게 되면 안된다.

우리는 큐(수업 진행중)를 통해 '끝나는 시간'이 더 빠른 수업을 알아야한다. 그래야 정렬된 수업(아직 강의실에 배치하지 않은 수업들)의 '시작 시간'을 '끝나는 시간'과 비교하여 같은 강의실에서 수업을 연달아 듣도록 하는 최적화 작업을 해야하기 때문이다.

만약 (수업 시작 시간, 수업 끝나는 시간)의 형태로 큐에 삽입하면 '시작 시간'을 기준으로 '시작 시간'이 더 빠른 수업이 큐에 앞쪽에 오게 된다. 이렇게 되면 강의실이 비는 타임에 수업을 들을 수 있음에도 불구하고, 해당 수업을 비는 강의실에 배치하지 않고 그냥 넘어가는 상황이 발생한다.



코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())
lessons = [list(map(int, input().split())) for _ in range(N)]

# '수업 시작 시간' 기준으로 오름차순 정렬
lessons = sorted(lessons, key=lambda x: x[0])

q = []
for lesson in lessons:
    # 이전 수업이 끝나는 시간과 다음 수업이 시작하는 시간을 비교
    if q and q[0] <= lesson[0]:
        heapq.heappop(q)
    heapq.heappush(q, lesson[1])

# 큐의 각각 원소는 한 강의실에서 하나의 수업이 진행중이라고 생각하면 쉽다.
# 즉, 큐의 사이즈가 강의실의 개수가 된다.
print(len(q))
profile
A Student of Computer Science

관심 있을 만한 포스트

0개의 댓글