[백준 11000번] 강의실 배정 (java)

알고리즘 : 그리디 알고리즘, 정렬, 우선순위 큐

 

처음에 시간초과가 나서 다른 블로그를 참고해 해결하였다. 개인적으로 어려웠던 문제였다.

백준 : 1931번 회의실 배정 문제 와 달리 이번 문제는 시작시간 기준으로 정렬을 해야한다.

 

시작시간과 종료시간을 강의정보로 갖는 갖는 Lecture 라는 클래스를 만들어줬다.

그리고 강의들을 저장하는 lectures 배열이 필요하다.

lectures 배열에 강의들을 시작시간을 기준으로 오름차순 정렬을 한다.

(위의 예제로 예를 들면 lectures 배열에는 (1,3) -> (2,4) -> (3,5) 순으로 정렬됨)

 

이 문제에서 구하고자 하는 것은 최소 사용할 수 있는 '강의실 수' 이다. 

이 문제에서 중요한건 우선순위 큐를 사용한다는 것이다.

우선순위 큐는 강의실에 이미 배정된 강의들 중 가장 짧은 종료시간을 반환한다.

 

- 우선순위 큐의 원소 개수 : 현재까지 배정된 강의실 개수

- 우선순위 큐의 원소 : 현재 강의실에 배정된 강의의 마지막 종료시간

 

lectures 배열은 아직 강의실을 배정받지 못한, 즉 대기중인 강의들이다.

그리고 lectures 배열의 첫번째 강의부터 마지막 강의까지, 매번 빈 강의실이 있는지 검사하고 

 

1. 빈 강의실이 있으면, 그 강의실에 배정

2. 빈 강의실이 없으면, 새로운 강의실에 배정

 

하는 방식으로 진행된다.

 

[예시]

예를 들어, 4개의 강의가 있고 각각의 강의는 (시작시간 = 1,종료시간 = 3) (2,4) (3,6) (5,7) 이라고 하자.

 

<1>

lectures 배열에 강의들을 넣고 정렬해준다.

정렬 결과 : 

  lectures[0] = Lecture(1,3)

  lectures[1] = Lecture(2,4)

  lectures[2] = Lecture(3,6)

  lectures[3] = Lecture(5,7)

 

<2>

우선 제일 일찍 끝나는 강의를 빈 강의실에 배정한다.

이 예제에서는 첫번째 강의가 종료시간 3 으로 제일 일찍 끝난다.

빈 강의실에 배정하는 행위는 우선순위 큐에 해당 강의의 종료시간을 넣는 것이다.

pq.offer(lectures[0].end) (여기서 pq는 우선순위 큐)

 

<3> 

이제 lectures 배열을 반복문으로 돌면서 하나하나씩 강의를 강의실에 배정해보자.

이때 주의할 것은 lectures[0] 강의는 이미 강의실에 배정했다. 그러므로 lectures[1] 부터 탐색하자.

lectures[1] = (시작시간 = 2, 종료시간 = 4)

pq.peek() = 3

이 강의를 첫 번째 강의가 있던 강의실에 넣을 수 있을까?

넣을 수 없다. 첫번째 강의의 종료시간은 3인데, 이 강의는 2에 시작하기 때문이다.

그러면? 새로운 강의실에 배정한다. 

pq.offer(lectures[1].end)

 

현재까지 강의실 2곳에 강의를 배정했다. pq.size() = 2

 

<4>

이제 세번째 강의 차례이다.

lectures[2] = (시작시간 = 3, 종료시간 = 6)

pq.peek() = 3

이 강의를 기존의 두 강의실 중 하나에 넣을 수 있을까?

넣을 수 있다. 첫 번째강의의 종료시간이 3이고, 이 강의는 3에 시작하기 때문이다.

그러면 첫 번째 강의는 끝났으니까 우선순위 큐에서 빼자.

pq.poll()

그리고 세번째 강의를 이 강의실에 넣자.

pq.offer(lectures[2].end)

 

현재까지 강의실 2곳에 강의 3개를 배정했다. pq.size() = 2

 

<5>

이제 마지막 강의 차례이다.

lectures[3] = (시작시간 = 5, 종료시간 = 7)

pq.peek() = 4

이 마지막 강의를 기존의 두 강의실 중 하나에 넣을 수 있을까?

넣을 수 있다. 두 번째 강의의 종료시간이 4이고, 이 마지막 강의는 5에 시작하기 때문이다.

그러면 두 번째 강의는 끝났으니까 우선순위 큐에서 빼자.

pq.poll()

그리고 마지막 강의를 이 강의실에 넣자.

pq.offer(lectures[3].end)

 

현재까지 강의실 2곳에 강의 4개를 배정했다. pq.size() = 2

 

<6>

전체 강의를 모두 강의실에 배정했으므로 반복문이 종료된다.

최종적으로 우선순위 큐에 남아있는 개수는 2이므로

우리가 4개의 강의를 배정하는 동안 사용한 총 강의실 수는 2곳이다.

 

 

[소스코드]