[그리디 알고리즘14] 백준 11000 강의실 배정 문제 풀이 파이썬

 

백준 11000 강의실 배정 

 

📜 문제 

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

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

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

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

 

🚩 입력 

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

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

 

🌞 출력

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

 

👵풀이

처음에 for문, 이중 for문으로 하다가 시간 초과가 나왔다. 결국 정답은 heapq을 사용해서 시간을 줄여 출력하는 것이었다. heapq을 아직 100% 알지 못해서 정답 코드를 보고도 궁금증이 계속 되었다. 

 

먼저 heapq 의 배열은 첫 번째 요소가 항상 가장 작은 요소로 배치되는 걸 알아야 유용하게 사용할 수 있다. 아래 예시 코드를 보면 첫 번째 요소는 항상 가장 작은 요소, 나머지는 랜덤이다. 

push 라고해서 가장 끝에 붙이는 줄 알았는데 아니었다. 

 

a = []
heapq.heappush(a, 10)
print(a)
heapq.heappush(a, 7)
print(a)
heapq.heappush(a,5 )
print(a)
heapq.heappush(a,3 )
print(a)
heapq.heappush(a,9 )
print(a)
heapq.heappush(a, 1)
print(a)

 

강의실 배정은 시작 시간과 끝나는 시간이 주어진다.  주어진 모든 과목은 반드시 진행되어야 한다. 

1. heapq, sys 를 import 한다. 

2. 입력받은 수업 시간표를 리스트 arr에  담는다

3. 해당 배열을 sort() 로 시작시간을 기준으로 정렬한다.

4. Q 라는 변수에 heapq 을 사용하여 arr 리스트의 가장 첫 요소 (시작시간이 가장 빠른) 의 끝나는 시간을 넣는다. 

5. 이제 arr 배열의 두 번째 요소 (index: 1) 부터 for문으로 Q의 첫번째 요소 (끝나는 시간을 넣는 heapq 리스트 )와 비교하여 Q의 첫번째 요소보다 arr[i][0] 비교하는 시작 시간이 같거나 크면 해당 과목을 시작할 수 있다. 

=> Q 리스트에 heappop()으로 가장 작은 요소를 꺼내고 heappush로 해당 과목의 끝나는 시점을 다시 넣는다. 

6. 반복 - > len(Q) 를 출력한다. 

 

** 중요한 점은 Q 리스트에서 Q[0] 과 비교를 한다. 위에서 언급했듯이 heapq 자료는 첫 요소가 가장 작은 요소를 배치한다. 가장 작은요소와 비교함으로써 Q[0] 이외의 다른 요소들과 비교할 필요가 없어진다. 다른 요소들은 어차피 Q[0]보다 클 것이기 때문에 ! 

비교하는 arr의 요소 대상(arr[i][0]이 Q[0]과 같거나 더 크다면 ---> 이는 Q 리스트 안의 모든 요소들보다 같거나 크다는 의미이다.  => 그리고 heapqpop()으로 가장 작은 요소를 빼내고 새로운 arr[i][1] 끝 시간을 넣는다. 

 

 

🥕 정답 코드 

1) heapq 

import heapq
import sys
input = sys.stdin.readline
n = int(input())

arr = [list(map(int,input().split())) for _ in range(n)]
arr.sort()

Q = []
heapq.heappush(Q,arr[0][1])

for i in range(1,n):
    if Q[0]>arr[i][0]:
        heapq.heappush(Q,arr[i][1])
    else:
        heapq.heappop(Q)
        heapq.heappush(Q,arr[i][1])

print(len(Q))

 

2) tuple로 푼 경우 + 공통의 heapq.heappush를 뺐을 때 코드가 짧아지고 속도도 빨라진다. 

import heapq
import sys
input = sys.stdin.readline
n= int(input())
arr = [tuple(map(int,input().split())) for _ in range(n)]

Q =[0]
for a,b in sorted(arr):
    if Q[0]<=a:
        heapq.heappop(Q)
    heapq.heappush(Q,b)

print(len(Q))