[Python 문제 풀이] 프로그래머스 '호텔 대실'

Programmers Lv.2 '호텔 대실' 파이썬 코드 및 풀이

조건 파악

1. N은 최대 1,000이므로 시간복잡도 O(N^2)만 되어도 풀 수 있다.

 

2. book_time[i]의 각 원소가 HH:MM이기 때문에 그대로 정렬해도 원하는 결과를 얻을 수 있다.

 

접근

1. 모든 객실의 타임테이블을 알아야 하는 것은 아니다. 필요한 최소 객실의 수는 즉, 동시에 이용하는 최대 객실의 수이다.

 

 

2. 위 그림과 같이 시간축을 따라 이용중인 객실의 수를 세보면 최대값을 알 수 있을 것이다.

 

3. 로직은 예약자를 입실시켜서 이용중인 방이 늘어나는가 아닌가 이 두 가지를 구분하는 것이다.

 

4. 이용중인 최대 객실의 수를 알아내는 것이기 때문에 이용중인 객실이 줄어드는 것은 고려할 필요가 없다.

 

의사코드

입실시각을 기준으로 예약명단을 정렬한다.

빠른입실부터 객실을 점유시킨다.

새로운 예약자를 객실에 배정할 때 퇴실한 예약자가 있는지를 확인한다.

아무도 퇴실하지 않았으면 이용중인 객실 수를 증가시킨다.

 

구현

from heapq import heappop, heappush

def solution(book_time):
    rooms = []
    book_time.sort(key = lambda _:_[0])
    for book in book_time :
        check_in = num(book[0])
        check_out = num(book[1]) + 10
        if len(rooms) != 0 and rooms[0] <= check_in :
            heappop(rooms)
        heappush(rooms,check_out)
    return len(rooms)

def num(HHMM) :
    return 60*int(HHMM[:2]) + int(HHMM[3:])

 

O(N)의 시간복잡도로 풀 수 있다.