[Level 2] 호텔 대실(Python)

프로그래머스

문제

최소한의 객실 만을 사용해 예약 손님을 받는다.
한 번 사용한 객실은 '퇴실 시간'을 기준으로 10분 후 다음 손님이 사용 가능
-> 코니에게 필요한 최소 객실의 수를 반환

 

<제한 사항>

1 ≤ book_time의 길이 ≤ 1,000
- book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 [대실 시작 시각, 대실 종료 시각]
- "00:00"부터 "23:59"까지로 주어진다.

 

풀이과정

풀이 시간: 20분

알고리즘: 그리디

1. 시작 시각을 기준으로 오름차순 정렬
2. 시각을 하나씩 확인하며 객실 배정
- 힙(종료시각)이 비어있다면 객실 추가
- 힙이 비어있지 않다면 힙에서 가장 빠른 종료 시각과 시작 시각을 비교
    - 시작 시각이 퇴실이 가장 빠른 객실의 종료 시각 + 10분 이후라면 해당 객실 사용 가능 -> heap에서 해당 객실의 종료시각 업데이트
    - 시작 시각이 퇴실이 가장 빠른 객실의 종료 시각 + 10분 이전이라면 새로운 객실 추가 배정 -> answer + 1

 

시간 복잡도: O(NlogN)

예약 시각 문자열 배열 정렬: O(NlogN)
각 예약에 대한 힙 연산: O(NlogK)
- K는 힙의 크기(최악의 경우, K는 N과 같을 수 있다. K<=N)
-> 전체 시간복잡도: O(NlogN)+O(NlogN)=O(NlogN)

 

코드

import heapq


def time_to_minutes(time_str: str) ->  str:
    hh, mm = map(int, time_str.split(':'))
    return hh * 60 + mm


def solution(book_time: list) -> int:
    """
    :param book_time: 예약 시간이 문자열 형태로 담긴 2차원 배열
    :return: 코니에게 필요한 최소 객실의 수
    """
    answer = 0 # 코니에게 필요한 최소 객실의 수
    # 1. 시작 시각을 기준으로 오름차순 정렬
    book_time.sort(key=lambda x: x[0])
    heap = [] # 각 객실의 종료 시각이 담긴 최소힙
    # 2. 시각을 하나씩 확인하며 객실 배정
    for start, end in book_time:
        start_time = time_to_minutes(start)
        end_time = time_to_minutes(end) + 10

        # 힙이 비어있지 않으면(사용할 객실이 있음)서, 가장 빨리 퇴실하는 객실의 퇴실 시각 + 10분 이후에 입실하려고 한다면, 해당 객실을 사용(퇴실 시각 업데이트)
        if heap and start_time >= heap[0]:
            heapq.heappop(heap)
        else: # 힙이 비어있거나, 가장 빨리 퇴실하는 객실의 시간보다 더 빨리 입실을 원하는 경우 (이어서 사용할 객실이 없기 때문에) 새로운 객실 추가
            answer += 1

        heapq.heappush(heap, end_time)

    return answer

 

백준의 회의실 배정, 순회 강연과 비슷한 유형의 그리디 문제라 쉽게 풀 수 있었다.

같이 문제를 푼 다른 분이 datetime 모듈을 사용해서 풀이하시면서 예제는 통과되는데 2, 3, 4, 6, 7, 8, 10, 11, 12 테스트케이스에서 실패한다고 하셔서 반례를 생각해보니 book_time = [["00:00", "23:55"], ["23:50", "23:59"]] 다음과 같은 반례를 찾을 수 있었다.

(위 테스트 케이스들이 통과되지 않는다면, 다음의 경우 2를 반환하는지 확인해볼 것)

 

check_out = datetime.strptime(check_out, "%H:%M")

next_available_time = (check_out + timedelta(minutes=10)).time()

이처럼 time 메서드로 변환하게 되면, 퇴실 시각인 23:55이 24:05로 변환되는 것이 아닌 00:05로 변환되고, 23:50 입실하려는 손님은 해당 객실에 배정될 수 없음에도 해당 객실을 할당해주게 된다.

 

개인적인 생각으로, datetime은 쓸 때마다 예상과 다르게 동작하는 부분이 은근히 많아서 꼭 공식문서를 꼼꼼히 확인해보고 사용하는 것이 좋다. 알고리즘 문제에서는 웬만하면 datetime을 사용하기보다 최소단위의 시간으로 변환해서 푸는게 더 편리하다고 생각된다.