[프로그래머스] Lv2. 호텔 대실

호텔 대실

문제 설명

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
    • [대실 시작 시각, 대실 종료 시각] 형태입니다.
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

---

입출력 예book_timeresult

[["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]	3
[["09:10", "10:10"], ["10:20", "12:20"]]	1
[["10:20", "12:30"], ["10:20", "12:30"], ["10:20", "12:30"]]	3

---

입출력 예 설명

입출력 예 #1

위 사진과 같습니다.

입출력 예 #2

첫 번째 손님이 10시 10분에 퇴실 후 10분간 청소한 뒤 두 번째 손님이 10시 20분에 입실하여 사용할 수 있으므로 방은 1개만 필요합니다.

입출력 예 #3

세 손님 모두 동일한 시간대를 예약했기 때문에 3개의 방이 필요합니다.

 

정답 풀이

from datetime import datetime, timedelta

def solution(book_time):
    answer = 0
    rooms = []
    
    book_time.sort(key=lambda x:x[0])
    
    def add_10_minutes(time):
        return time + timedelta(minutes=10)
    
    for start, end in book_time:
        start_dt = datetime.strptime(start, '%H:%M')
        end_dt = datetime.strptime(end, '%H:%M')
        start_possible = add_10_minutes(end_dt)
        print(start_possible)
        if len(rooms) == 0:
            rooms.append(start_possible)
            answer += 1
        else:
            for i in range(len(rooms)):
                if rooms[i] <= start_dt:
                    rooms[i] = start_possible
                    break
            else:
                rooms.append(start_possible)
                answer += 1
    return answer

 

로직은 맞는거 같은데 계속 틀렸을 때는 문자열끼리 대소를 비교했는데, 

datetime형식으로 대소를 비교하니까 통과되었다.

 

datetime형식으로 변환하고, timedelta를 이용하여 10분 후의 시간을 구한다. 

 

다른 사람 풀이

from heapq import heappop, heappush

def solution(book_time):
    answer = 1
    
    # "HH:MM" → HH * 60 + MM
    book_time_ref = [(int(s[:2]) * 60 + int(s[3:]), int(e[:2]) * 60 + int(e[3:])) for s, e in book_time]
    book_time_ref.sort()
    
    heap = []
    for s, e in book_time_ref:
        if not heap:
            heappush(heap,e+10)
            continue
        if heap[0] <= s:
            heappop(heap)
        else:
            answer += 1
        heappush(heap,e+10)
    
    return answer

시간 형식으로 사용하지 않고, 분단위로 바꾸어서 대소를 비교하는게 더 좋은 방법인거 같다.

그리고 heap을 통해서 가장 빠른 퇴실을 찾아서 계산하는게 내 방식보다 더 좋아보인다.