[프로그래머스] 155651. 호텔 대실 | 정렬, 우선순위큐 | 파이썬, 소스코드, 정답

 

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

프로그래머스

---

문제 요약

• 호텔 예약 시간(입실시간, 퇴실시간) 리스트가 주어진다. 
• 모든 손님을 받기 위해 필요한 최소한의 객실 수를 구하라.

---

문제 조건

• 손님이 퇴실한 후 10분뒤부터 다른 손님이 입실가능하다.
• 주어지는 입실시간/퇴실시간의 형태는 "hh:mm"이다
• 예약시간이 자정을 넘어가는 일은 없다. 시작시간은 종료시간보다 항상 빠르다

---

시행착오

• 문제를 읽을 때 정렬해야 한다는 것을 깨달았다.
• 문제를 풀다가 객실 이용가능시간(퇴실시간+10분)을 관리하기 위해 우선순위 큐를 사용해야한다는 것을 알았다.

---

접근방법

1. 시간을 편리하게 관리하기 위해 분단위로 변환한다.
2. 예약시간을 입실시간 기준 오름차순 정렬한다.
3. 입실가능한 시간을 관리하는 우선순위큐를 만든다
4. 입실가능한 방이 있는지 확인하고 있으면 그 방으로 들어가고 없으면 새로운 방을 배정한다.

 

---

소스코드

from queue import PriorityQueue

def getTime(s):
    return int(s[:2])*60 + int(s[3:])

def solution(book_time):
    max_num_of_rooms = 0
    available_times = PriorityQueue()
    book_time.sort()

    for book in book_time:
        for available_time in available_times.queue:
            if available_time <= getTime(book[0]):
                available_times.get()
                available_times.put(getTime(book[1]) + 10)
                break
        else:
            available_times.put(getTime(book[1]) + 10)
            max_num_of_rooms = max(max_num_of_rooms, available_times.qsize())

    return max_num_of_rooms