[백준] 1379 강의실 2 [Python]

 

이 문제의 분류는 그리디 알고리즘과 우선순위 큐를 활용해서 푸는 문제입니다. 그리디 알고리즘만 사용하고 우선순위 큐를 사용하지 않는다면 시간초과가 나서 우선순위 큐를 사용하는 방법으로 구현해봤습니다.

 

k = int(s.readline())
#우선 순위 큐 저장 배열선언
heap =[]
#출력값들을 저장할 배열선언
answer= [0] * (k+1)
lecture = [list(map(int,s.readline().split())) for _ in range(k)]

#강의를 시작시간과 끝나는시간 기준으로 정렬
lecture.sort(key=lambda x:(x[1],x[2]))

 

강의를 시작시간과 끝나는시간으로 정렬하고 heap에 넣어야 새로운 강의를 넣을 때 마다 비교가 가능하므로 정렬해준다.

 

#1은 강의실번호 
room_num=1
#끝나는 시간과 강의실 번호를 heap에 저장
hq.heappush(heap,[lecture[0][2],room_num])
#강의번호는 lecture배열의 첫번쨰 값
answer[lecture[0][0]] = room_num

 

강의실 번호를 세기위해 room_num이라는 변수를 생성해주고 강의 번호를 출력해줄 answer배열에 저장.

 

for i in range(1,k):
    # 끝나는 시간보다 강의 시작시간이 작으면 heap에 push
    if heap[0][0] > lecture[i][1]:
        room_num +=1   
        answer[lecture[i][0]] = room_num
        hq.heappush(heap,[lecture[i][2] ,room_num])
    # 끝나는 시간보다 강의 시작시간이 크면 heappop하고 그 강의실번호를
    # 새로 넣는 heap에 전달
    else:
        temp = hq.heappop(heap)
        answer[lecture[i][0]] = temp[1]
        hq.heappush(heap,[lecture[i][2],temp[1]])

 

k수만큼 반복하면서 끝나는 시간과 시작 시간을 비교하면서 끝나는 시간이 시작 시간보다 작은 값이 heap에 존재하면 pop해주고 push해주는 과정을 반복합니다. 이 과정을 하면서 빈 강의실을 사용해서 최대 강의실 번호를 유지할 수 있습니다.

 

전체코드

from sys import stdin as s
import heapq as hq
s=open("input.txt","rt")

k = int(s.readline())
#우선 순위 큐 저장 배열선언
heap =[]
#출력값들을 저장할 배열선언
answer= [0] * (k+1)
lecture = [list(map(int,s.readline().split())) for _ in range(k)]

#강의를 시작시간과 끝나는시간 기준으로 정렬
lecture.sort(key=lambda x:(x[1],x[2]))

#1은 강의실번호 
room_num=1
#끝나는 시간과 강의실 번호를 heap에 저장
hq.heappush(heap,[lecture[0][2],room_num])
#강의번호는 lecture배열의 첫번쨰 값
answer[lecture[0][0]] = room_num


for i in range(1,k):
    # 끝나는 시간보다 강의 시작시간이 작으면 heap에 push
    if heap[0][0] > lecture[i][1]:
        room_num +=1   
        answer[lecture[i][0]] = room_num
        hq.heappush(heap,[lecture[i][2] ,room_num])
    # 끝나는 시간보다 강의 시작시간이 크면 heappop하고 그 강의실번호를
    # 새로 넣는 heap에 전달
    else:
        temp = hq.heappop(heap)
        answer[lecture[i][0]] = temp[1]
        hq.heappush(heap,[lecture[i][2],temp[1]])


print(len(heap))
for i in range(1,len(answer)):
    print(answer[i])