프로그래머스 - 호텔 대실(정렬, 우선순위 큐) / Level 2 / Python

문제 📋

프로그래머스 - 호텔 대실

풀이 📝

import heapq


class Room:
    def __init__(self, ready_time):
        self.ready_time = ready_time
    
    def __lt__(self, other):
        if self.ready_time < other.ready_time:
            return True
        else:
            return False

        
def solution(book_time):
    max_room_cnt = 0
    hotel = []
    
    for i in range(len(book_time)):
        hour, minute = map(int, book_time[i][1].split(":"))
        minute += 10
        
        if minute >= 60:
            hour += 1
            minute -= 60
        
        hour = str(hour)
        minute = str(minute)
            
        if len(hour) == 1:
            hour = "0" + hour
        
        if len(minute) == 1:
            minute = "0" + minute
        
        book_time[i][1] = hour + ":" + minute
        
    book_time.sort()
    
    for start, end in book_time:
        if hotel:
            room = heapq.heappop(hotel)
            
            if start < room.ready_time:
                heapq.heappush(hotel, room)
                heapq.heappush(hotel, Room(end))
            else:
                room.ready_time = end
                heapq.heappush(hotel, room)
        else:
            heapq.heappush(hotel, Room(end))
        
        if len(hotel) > max_room_cnt:
            max_room_cnt = len(hotel)
                
    
    return max_room_cnt

1. 문제 정의
   호텔 대실 예약시간이 주어졌을 때 시간이 겹치지 않도록 필요한 최소 방의 개수를 구하는 문제이다.
   

2. 시간복잡도 계산
   for 문으로 한번 순회하면서 우선순위 큐에 삽입 삭제를 하기 때문에 시간복잡도는 최대 O(NlogN) 이다. book_time 배열의 길이가 최대 1,000이기 때문에 시간내에 통과할 것이라 판단했다.

3. 문제 풀이
   먼저 청소시간도 방을 사용할 수 없기 때문에 대실 종료 시각에 10분씩 더해주었다.
   그 다음 방을 최대한 활용하기 위해 book_time을 대실 시작 시간 기준으로 오름차순 정렬했다.

   우선순위 큐에서는 가장 종료 시간이 이른 Room을 꺼내서 방이 사용가능할 경우 Room의 대실 종료 시각을 지금 예약의 종료 시각으로 초기화 해주었고 방이 사용 불가능할 경우 새로운 방을 할당해 우선순위 큐에 넣어주었다.

4. 예외 사항
   주어진 시각들이 "00:00" ~ "23:59" 이었기 때문에 단순한 문자열 비교로도 대소를 판별할 수 있었다.