[BOJ 11000 파이썬] 강의실 배정

11000번: 강의실 배정

 

그리디 알고리즘에서 자주 보이는 유형이고,

 

코딩테스트 연습 - [1차] 추석 트래픽

카카오 2018 공개채용 코딩테스트 문제인 추석 트래픽 문제와 거진 비슷하게 보인다.

 

처음 이 문제를 보고 떠올려야할 생각은, 가장 빨리 끝나는 수업의 시간과 나머지 수업의 시작시간을 비교하는 것이다.

 

즉, 만약 가장 빨리 끝나는 수업보다 나머지 수업의 시작 시간이 더 작다면, 가장 빨리 끝나는 수업과 나머지 수업의 끝 시간을 비교해서 더 빨리 끝나는 시간을 비교해서 업데이트 해주어야한다.

만약 더 크다면 가장 빨리 끝나는 수업을 제거하고, 나머지 수업이 끝나는 시간을 넣어주어야한다.

 

말로는 이해가 잘 가지 않을텐데, 이를 순서대로 표현하면,

 

1. 수강신청한 수업들을 '시작 시간'을 기준으로 정렬한다.
2. 첫 번째 강의가 끝나는 시간을 우선순위 큐에 추가한다.
3. 강의 리스트의 1번째 인덱스부터 마지막까지 반복문을 실행한다
   1. 우선순위 큐에 첫 번째 인덱스에 접근 (항상 최솟값이다. heapq는 첫번째 값만 최솟값임을 보장하고 나머지 인덱스는 정렬되어있지 않음을 주의!!)
   2. 만약 강의의 시작시간이 우선순위 큐의 첫 번째 인덱스보다 작다면(강의 시간이 겹친다면) 해당 강의의 끝나는 시간을 우선순위 큐에 추가한다.
   3. 아니라면 우선순위 큐의 첫 번째 인덱스를 pop 한 후 해당 강의의 끝나는 시간을 우선순위 큐에 추가한다.(겹치지 않는다면 해당 강의는 끝났다고 생각하고 pop후 새로운 강의 push)

코드를 보면 더 자세한 이해가 될 것이다.

import heapq
import sys

N = int(sys.stdin.readline().rstrip())

time = []
hq = []

for i in range(0,N):
    S,T = map(int,sys.stdin.readline().rstrip().split())
    time.append((S,T))

time.sort()

heapq.heappush(hq,time[0][1])

for i in range(1,N):
    if  time[i][0] < hq[0]:
        heapq.heappush(hq,time[i][1])

    else:
        heapq.heappop(hq)
        heapq.heappush(hq,time[i][1])
        
print(len(hq))

 

생각을 떠올리긴 쉬웠지만.. 막상 구현하기는 매우 어려웠던 문제였다😢

생각이 안떠올랐다 하더라도 기억해두기에 좋은 문제 유형인 것 같다!!