[그리디 알고리즘] 백준 11000번 강의실 배정

백준 알고리즘 문제 원본 보기

문제

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

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

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

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

---

입력

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

이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

---

출력

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

---

예제 

예제 입력 1	예제 출력 1
3 1 3 2 4 3 5	2

---

아이디어

우선 가장 적은 강의실을 사용하여 수업을 배치하기 위해서는 시작 시간과 종료 시간이 빠른 수업을 우선적으로 배치해야 한다. 따라서 수업 시간을 시작시간을 기준으로, 시작시간이 동일한 경우 종료 시간을 기준으로 정렬하는 것을 우선으로 한다.

또한 한 강의실에 배치된 수업의 전체적인 종료시간(한 강의실에 배치된 수업 중 마지막 수업의 종료시간) 중 하나라도 A 수업의 수업 시작시간보다 빠르다면 A 수업을 해당 강의실에 배치할 수 있다.

모든 강의실의 전체적인 종료시간이 A 수업의 시작시간보다 느리다면 A 수업을 배치하기 위해서는 추가적인 강의실이 필요하다.(추가한 강의실의 전체적인 종료시간은 A 수업의 종료시간과 같다.)

---

변수 설명(솔루션과 코드)

N: 배치해야 하는 수업의 개수

Ti: i번째 수업의 시작 시간(i 는 0 ~ N-1)

Si: i번째 수업의 종료 시간(i 는 0 ~ N-1)

C: 모든 수업의 시작시간과 종료시간 ([Ti, Si])를 저장하는 배열

end: 각 강의실에 배치된 수업의 전체적인 종료 시간을 저장하는 배열

---

솔루션 1

* 해당 솔루션과 코드는 백준에 제출하였을 때 시간 초과가 발생합니다. 개념적인 솔루션 설명을 위해 추가하였습니다. 아래 이유와 해결된 코드까지 작성하였으니 아래 코드와 솔루션도 확인해주세요 :)

혹시 빠르게 솔루션과 해답 코드만을 확인하고 싶으시다면 가장 아래의 솔루션과 코드만 확인하세요 -!

 

C는 [Ti, Si]의 N개 수업 시작 시간, 종료 시간을 가지고 있다.

우선 C를 Ti(시작시간)기준,Ti가 동일한 경우 Si기준으로 정렬한다.

배열 end에 C배열의 가장 첫 원소의 종료시간을 추가한다. 다음 C의 원소의 Si가 배열end내의 최솟값와 같거나 end 배열 내 최솟값보다 큰 경우 end 내의 최솟값을 삭제하고 해당 원소의 Si를 end에 추가한다. (해당 원소 수업이 end 내의 최솟값을 전체적 종료 시간으로 가지던 강의실에 배치되었으므로 종료 시간이 해당 원소의 종료 시간으로 변경됨)

만약 end 배열 내 최솟값이 배열 C의 원소의 Ti보다 클 경우 현재 사용하는 강의실에는 해당 수업을 배치할 수 없으므로 하나의 강의실을 더 사용해야 한다. 따라서 해당 원소의 Si를 end 배열에 추가하여 새로 사용할 강의실의 종료시간을 해당 원소의 Si로 설정한다.

 

이러한 과정을 통해 end 내에는 모든 수업을 진행하기 위해 사용할 강의실 들의 최종 종료 시간이 모두 삽입되고, end의 크기, 즉 end 내에 저장된 종료 시간 수는 사용해야 하는 최소 강의실 수와 동일하다.

---

코드 1(Python)

N = int(input())
C = []
end = [0]
for i in range(N):
    C.append(list(map(int,input().split())))
C = sorted(C,key = lambda x: (x[0],x[1]))
for i in range(N):
    if C[i][0]>= min(end):
        end.remove(min(end))
        end.append(C[i][1])
    else :
        end.append(C[i][1])
print(len(end))

---

솔루션 2

* 해당 솔루션과 코드는 백준에 제출하였을 때 런타임에러가 발생합니다. Priority Queue의 개념 설명을 위해 추가하였습니다. 아래 이유와 해결된 코드까지 작성하였으니 아래 코드와 솔루션도 확인해주세요 :)

혹시 빠르게 솔루션과 해답 코드만을 확인하고 싶으시다면 가장 아래의 솔루션과 코드만 확인하세요 -!

 

현재 min(end)은 배열에서 가장 작은 원소를 탐색하는 작업이다. min 작업의 시간 복잡도는 리스트에 포함되어 있는 원소의 수와 같으므로 O(N)이다.

또한 end.remove(a)은 end 내에 a라는 원소를 탐색하고 이를 찾아 리스트에서 삭제하는 작업으로 시간 복잡도는 위와 같이 O(N)이다.

이러한 함수를 사용한 위 코드에 시간 초과가 발생하기 때문에 '우선순위 큐'를 이용하여 시간 복잡도를 최소화 하는 방안을 이용하였다. Python에서 우선순위 큐는 queue 모듈 내의 PriorityQueue를 import하여 사용할 수 있다. PriorityQueue는 우선순위가 작은 원소가 높은 우선순위를 가지도록 설계되어 있다. 따라서 원소를 삽입할 때 자동적으로 우선 순위를 기준으로 오름차순 정렬하여 삽입하고 원소를 꺼낼 때(get이용) 우선순위가 가장 작은 원소 먼저 큐에서 꺼내진다.

python의 priority queue는 heapq 모듈을 통해 구현되어 있으며 힙과 동일하게 put(), get() 함수 들은 O(log n)의 시간 복잡도를 가진다.

 

Priority queue의 대표적인 내장함수(우선순위 큐 객체 명을 pque로 가정)

pque = PriorityQueue() : 우선순위 큐 초기화

pque.size(): 큐의 크기(큐에 저장된 원소의 개수)

pque.get(): 가장 우선순위가 작은 원소를 큐에서 꺼냄

pque.put(a): a를 pque에 삽입(우선순위 = a)

pque.put((a,b)): (a,b)를 pque에 삽입(우선순위 = a)

pque.queue[]: 우선순위 큐의 원소를 리스트와 동일하게 인덱스를 이용하여 접근할 수 있도록 함

---

코드 2(Python)

from queue import PriorityQueue

N = int(input())
C = []
pque = PriorityQueue()
for i in range(N):
    C.append(list(map(int,input().split())))
C = sorted(C,key = lambda x: (x[0],x[1]))

for i in range(N):
    if pque.qsize() != 0 and pque.queue[0][1]<= C[i][0]:
        pque.get()
    pque.put((C[i][1],C[i][1]))
    
print(pque.qsize())

---

솔루션 3

솔루션 2의 코드는 백준 온라인 저지에 제출할 경우 런타임에러가 발생한다. 이유를 찾아보던 와중 Queue 모듈을 지원하지 않기 때문이라는 글을 보고(확실하지는 않음! 혹시 다른 이유를 아시는 분들은 댓글 남겨주세요!) priority queue 구현을 위해 python의 내장 모듈인 heapq를 이용하였다.

heapq 자료 구조와 heapq 모듈 사용법은 다음 사이트를 참고하였다.

(https://www.daleseo.com/python-heapq/)

 

해당 사이트를 참고한 heapq 모듈에 대한 간단한 사용법(요약)

heapq 모듈은 보통 리스트를 최소 힙처럼 다룰 수 있도록 도와주는 모듈이다. 따라서 빈 리스트를 생성한 후 heapq 모듈의 함수 호출 시 리스트를 인자로 넘겨 최소 힙 자료구조로 동작하도록 한다.

즉, heapq 모듈을 이용해 원소를 추가, 삭제한 리스트는 최소 힙이라고 할 수 있다.

힙에 원소 추가: heapq.heappush(리스트명, 원소) -> 리스트에 원소를 추가

힙의 원소 삭제: heapq.heappop(리스트명) -> 리스트에서 가장 작은 원소를 삭제

* heapq 모듈에 사용되는 리스트는 python의 보통 리스트이므로 인덱스를 통해 접근해서 원소를 읽을 수 있음-> 주의사항: 두 번째 작은 원소는 heap[1]이 아닐 수 있음

---

코드 3(Python)

import heapq
import sys

N = int(input())
C = []
h = []
for i in range(N):
    C.append(list(map(int, sys.stdin.readline().split())))

C = sorted(C,key = lambda x: x[0])

for i in range(N):
    if len(h) != 0 and h[0]<= C[i][0]:
        heapq.heappop(h)
    heapq.heappush(h,C[i][1])
    
print(len(h))

---

간단한 문제임에도 모듈 사용과 시간 초과로 인해 우여곡절이 많았던 문제이다.

혹시 해당 문제로 어려움을 겪고 있다면 도움이 되기를 바란다.

 

설명에 잘못된 부분이 있거나 질문 사항이 있으시다면 언제든지 댓글 남겨주세요 :)