[BOJ] 백준 11000번 : 강의실 배정 (JAVA)

문제

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

 

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

 

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

 

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

 

 

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

 

이후 N개의 줄에 S_i, T_i가 주어진다. (1 ≤ S_i < T_i ≤ 10⁹)

 

 

출력

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

 

 

풀이

그리디 알고리즘과 우선순위 큐를 사용하여 풀 수 있는 문제였습니다.

 

 

강의실을 여러 개 사용하되, 강의가 겹치지 않게 최소한의 강의실을 배정하는 것이 목표입니다.

 

N은 200,000이기 때문에 단순하게 브루트포스를 돌리면 당연히 시간초과가 나고, 똑똑한 방식을 생각해야 합니다.

 

 

먼저, 어떻게 강의를 배정해야하는지부터 고민해 봅시다.

 

당연히, 버리는 시간을 최소로 하면서 강의를 배정해야 최소한의 강의실의 개수를 알아낼 수 있을 것입니다.

 

그렇다면, 어떻게 하면 버리는 시간을 최소로 할 수 있을까요?

 

 

방법은 바로 정렬입니다.

 

시작 시각을 기준으로 하거나, 종료 시각을 기준으로 할 수 있는데 시작 시각을 기준으로 오름차순 정렬해야 합니다.

 

종료 시각을 기준으로 하면 왜 안 되는지에 대해서는 포스팅 하단에 따로 적어두겠습니다.

 

특정 강의를 시작 시각을 기준으로 오름차순 정렬하되, 시간 시각이 같다면 종료 시각을 기준으로 오름차순 정렬한다면 아래와 같은 형태가 될 것입니다.

 

 

 

여기서 버려지는 시간을 색칠해 봅시다.

 

 

 

빨간색으로 칠한 영역이 강의를 배정할 수 없는 버려지는 시간입니다.

 

아무렇게나 강의실을 넣는 것보다 시작 시각으로 정렬을 해야 앞에서부터 차곡 차곡 강의 간의 텀을 짧게 하여 배정이 가능합니다.

 

 

이렇게 문제의 입력으로 들어온 강의 배열을 시작 시각을 기준으로 정렬이 끝났다면, 강의실이 몇 개가 필요한지 생각해봐야 합니다.

 

위의 그림에서 알 수 있듯이, 정렬 자체는 시작 시각을 기준으로 하였지만, 결국 어떤 강의가 들어갈 자리를 찾기 위해서는 현재 배정된 강의의 종료 시각과 비교하게 됩니다.

 

가령, A 강의가 1시부터 3시까지 진행하고, B 강의가 2시부터 4시까지 진행한다면, A 강의의 종료 시각이 3시고, B 강의의 시작 시각이 2시이므로 B 강의는 새로운 강의실에 배정해야 합니다.

 

그리고 항상 배정된 강의의 시작 시각보다 빠른 강의는 없으므로 강의가 겹치는 일도 생기지 않습니다.

 

 

위 로직을 구현하기 위해서는 우선순위 큐가 제격입니다.

 

우선순위 큐에 강의의 종료 시각을 넣어 두고, 정렬 기준은 오름차순으로 설정합니다.

 

그리고 배정이 되지 않은 강의의 시작 시각과 우선순위 큐 안에서 종료 시각이 가장 빠른 강의의 종료 시각과 비교합니다.

 

만약, 배정이 되지 않은 강의의 시작 시각이 우선순위 큐 안에서 종료 시각이 가장 빠른 강의의 종료 시각보다 늦다면, 현재 우선순위 큐에서 top에 있는 강의를 제거하고, 이 배정이 안 된 강의를 우선순위 큐에 넣는 것입니다.

 

이를, 다시 말하면 원래 있던 강의실에 다음 강의를 배정하는 것이죠.

 

반대의 경우는 우선순위 큐에서 top에 있는 강의는 냅두고, 배정이 안 된 강의를 우선순위 큐에 넣어 줍니다.

 

이것은 새로운 강의실에 강의를 배정하는 것과 일치합니다.

 

그리고 모든 강의가 배정이 되었다면, 우선순위 큐의 사이즈를 반환하면 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

 

종료 시각을 기준으로 정렬하면 안 되는 이유

명확하게 그림으로 설명은 못 하겠으나, 명백한 반례가 존재합니다.

 

N이 6이고, 강의 시간이 아래와 같은 경우가 반례입니다.

 

 

1 3

 

2 5

 

7 8

 

9 10

 

7 11

 

4 12

 

 

우선순위 큐에 넣는 로직은 동일합니다.

 

결국, 큐의 top에 위치한 강의의 종료 시각과 배정이 안 된 강의의 시작 시각과 비교하는 것이죠.

 

먼저, (1, 3)은 첫 번째 강의실에 배정됩니다.

 

그리고 (2, 5)의 시작 시각은 2시고, (1, 3)이 종료 시각은 3시이므로 두 번째 강의실에 배정됩니다.

 

(7, 8)의 시작 시각은 7시고, (1, 3)의 종료 시각은 3시이므로 큐에서 (1, 3)을 제거한 후 (7, 8)을 집어 넣습니다. 즉, (7, 8)은 첫 번째 강의실에 배정됩니다.

 

(9, 10)의 시작 시각은 9시고, (2, 5)의 종료 시각은 5시이므로 큐에서 (2, 5)을 제거 한 후 (9, 10)을 집어 넣습니다. 즉, (9, 10)은 두 번째 강의실에 배정됩니다.

 

(7, 11)의 시작 시각은 7시고, (7, 8)의 종료 시각은 8시이므로 세 번째 강의실에 배정됩니다.

 

(4, 12)의 시작 시각은 4시고, (7, 8)의 종료 시각은 8시이므로 네 번째 강의실에 배정됩니다.

 

따라서, 필요한 강의실의 개수는 4개가 됩니다.

 

 

하지만.. 이것은 최소의 개수가 아닙니다.

 

연습해보실 겸, 시작 시각을 기준으로 정렬하여 강의를 배정해 보시면 강의실의 개수가 3개가 나온다는 사실을 알 수 있습니다.

 

따라서 종료 시각을 기준으로 정렬하면 틀립니다!!

 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.