프로그래머스 - 호텔 대실 (파이썬)

1. heapq 사용

heapq를 사용하면 우선순위큐처럼 값을 저장 시 오름차순으로 정렬되는 장점이 있다.

먼저 book_time 배열의 시간,분 값을 분단위로 합친후 대실시작시간을 기준으로 정렬한다.

heapq를 사용하여 queue를 만든다. 방 개수만큼 큐 인덱스가 늘어나고, 해당 방의 대실 종료시간이 값으로 들어간다.

queue에 값이 없거나 queue의 첫번째 값이 대실시작시간보다 크면 queue에  book_time의 대실 종료시간+10을 queue에 넣는다. 그렇지 않다면 queue에서 첫번째 인덱스를 빼고 해당 book_time의 대실 종료시간+10을 queue에 넣는다.( 해당 방을 book_time[i]가 빌릴 수 있으므로 방을 하나 늘리지 않고 해당 방의 대실종료시간을 업뎃하는 의미로 생각한다.)

 

import heapq
def solution(book_time):
    answer = 1
    heap=[]
    book_time=[[int(i[:2])*60+int(i[3:]),int(j[:2])*60+int(j[3:])] for i,j in book_time]
    book_time.sort()
    for book in book_time:
        if not heap:
            heapq.heappush(heap,book[1]+10)
            continue
        elif heap[0]<=book[0]:
            heapq.heappop(heap)
        else:
            answer+=1
        heapq.heappush(heap,book[1]+10)
    return answer