[Programmers] 호텔 대실

문제

요약

입실, 퇴실 시간이 주어질 때, 최소 몇개의 방이 필요한지 구하시오.

퇴실 이후 10분 간은 청소시간임.

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

 

---

풀이

이 문제를 풀면서 잊고 있었던 heapq를 떠올리게 되었다.

뭐든 안잊어 버리도록 꾸준히 사용하는 것이 중요한 것 같다.

 

풀이에 대해서 설명해보자면 우선 입실 시간 기준으로 정렬해준다.

입실시간 순서대로 정렬되면 앞의 퇴실 시간이랑 뒤의 입실시간이 겹치는 지만 확인하면 된다.

Heapq는 새로운 요소를 추가해주면 가장 작은 것을 가장 최상단 노드에 배치하는 최소힙 구조를 갖기 때문에

가장 빠른 퇴실 시간과 비교하는 현재의 입실시간을 비교해서 겹치지 않으면 해당 사람 이후에 이 사람이 입실한다고 봐도 무방하다.

힙큐의 구조와 방식을 손으로 그려보면 금방 이해되는 문제였다.

from heapq import heappop, heappush
def solution(book_time):
    rooms = []
    book_time.sort(key=lambda x:x[0])
    
    for book in book_time:
        a, b = book[0], book[1]
        chkin = int(a[:2]) * 60 + int(a[3:])
        chkout = int(b[:2]) * 60 + int(b[3:]) + 10
        if rooms and rooms[0] <= chkin:
            heappop(rooms)
        heappush(rooms, chkout)
    
    return len(rooms)