[BOJ] 11000번 - 강의실 배정

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력

• 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
• 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 10^9)

출력

• 강의실의 개수를 출력하라.

 

🚦 문제 유형

• Greedy 알고리즘

 

✏️ Solution

문제 속 빨간색으로 표시된 부분에서 풀이방법에 대한 힌트를 얻을 수 있다.

먼저, 최소의 강의실을 사용하려면 모든 수업마다 강의실을 잡는게 아니라 한 강의실에 최대한 많은 강의가 가능하도록 만들어야 한다.

그리고 수업이 끝난 직후에 다음 수업을 시작할수 있으므로 수업의 시작시간, 끝나는 시간을 비교해서 강의실을 새로 배정받아야 하는 지를 체크해야 한다.

따라서 1번 수업이 끝난 직후 2번 수업이 시작될 수 있다면 1번이 썼던 강의실을 2번이 쓰면 된다.

 

하지만, 어떤 강의 시작시간을 강의 리스트안의 모든 강의가 끝나는 시간과 비교할 필요는 없다.

만약 다음 강의의 시작시간이 이전 강의의 끝나는 시간보다 이른 상황이 여러 개라면, 그때마다 강의실을 배정해야 하기 때문이다.

이것은 최소의 강의실을 만드는 조건에 모순된다.

이전 강의가 끝나는 시간이 다음 강의가 시작하는 시간보다 이르다면, 바로 강의실을 이어서 쓸 수 있기 때문에

끝나는 시간이 가장 이른 강의실만 확인하면 된다. (그리디 방법)

여기서 바로 우선순위 큐를 사용할 수 있다.

문제 풀이 순서는 다음과 같다.

1. 강의 리스트를 강의 시작이 이른 순서대로 정렬한다.
2. 우선순위 큐를 만들어 첫번째 강의 끝나는 시간을 추가한다.
3. 강의 리스트의 1번째 부터 마지막까지 반복문을 실행한다.
   1. 우선순위 큐 첫번째 원소(=첫번째 강의시간이 끝나는 시간)에 접근한다.
   2. 현재 보는 강의 시작 시간이 우선순위 큐의 첫번째 원소보다 작다면, 현재보는 강의시간의 끝나는 시간을 우선순위 큐에 추가한다.
   3. 그게 아니라면, 우선순위 큐의 첫번째 원소를 큐에서 삭제하고 현재보는 강의 시간의 끝나는 시간을 우선순위 큐에 추가한다.

import sys
import heapq

N = int(sys.stdin.readline())
sbj = []	# 강의 리스트
for i in range(N):
    sbj.append(list(map(int, sys.stdin.readline().strip().split(' '))))
sbj.sort()	# 강의 시작 시간이 이른 순서대로 정렬

sbj_queue = []	# 강의 끝나는 시간이 담긴 우선순위 큐
heapq.heappush(sbj_queue, sbj[0][1])

for i in range(1, N):
    if sbj[i][0] < sbj_queue[0]:
        heapq.heappush(sbj_queue, sbj[i][1])
    else:
        heapq.heappop(sbj_queue)
        heapq.heappush(sbj_queue, sbj[i][1])
print(len(sbj_queue))

 

⚙️ Review

처음에 시도했던 풀이 방법은 그리디를 잘 활용하지 못해 시간초과를 만났었다.

다음 강의의 시작시간이 이전 강의가 끝나는 시간보다 이르면, 강의실 리스트에 다음 강의실의 끝나는 시간을 추가했고,

그렇지 않으면, 강의실 리스트 원소들과 비교하여 강의실 리스트의 원소들을 끝나는 시간으로 업데이트 했다.

즉, 이 문제는 그리디 알고리즘으로 가장 빠르게 끝나는 시간만 확인하면 되는데 다른 강의의 끝나는 시간까지 체크해버리는 바람에 비효율적 풀이가 된 것이다.

아래는 처음에 시도했던 풀이 방법이고 우선순위 큐를 사용하지 않은 것 빼고 나머지는 동일하다.

# 시간초과
room = [sbj[0][1]]      # 첫번째 원소
for i in range(1, N):
    for j in range(len(room)):
        if  sbj[i][0] >= room[j]:
            room[j]= sbj[i][1]
            break
        else:
            room.append(sbj[i][1])
print(len((room)))

역시 알고리즘은 아이디어와 자료구조를 잘 연결시킬 수 있어야 하는 것 같다.

자료구조를 활용할 수 있는 능력을 더 키워야 겠다고 다짐했다.