[Python] 프로그래머스 Lv2_호텔 대실

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

프로그래머스

 

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

제한사항

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

 

"""
입출력 예시)

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

 

# book_time = [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]] -> 3

 

 

## 의사코드 ##

# HH:MM 형태를 분으로 계산 -> HH * 60 + MM
# [(int(s[:2])*60 + int(s[3:]), int(e[:2])*60 + int(e[3:])) for s, e in book_time]

# 대실 시작 시간을 기준으로 정렬 
# book_time.sort(key=lambda x: x[0])

# 다음 손님 이용 가능 시각: 대실 종료 시각 + 10분

# 종료 시각이 가장 빠른 객실을 선택
# heapq 이용 -> 최소 힙
# import heapq
# heapq.heappush(heap, 종료 시각)

# 할당할 객실은 종료 시각이 가장 빠른 객실로 선택
# heap[0]

# 다음 손님의 시작 시각이 이전 손님의 종료 시각 이후인 경우, 해당 객실 할당
# if heap[0] <= s:
#     heapq.heappop(heap)

# 다음 손님의 시작 시각이 이전 손님의 종료 시각 이전인 경우, 새로운 객실 할당
# else:
#     answer += 1
# heapq.heappush(heap, e+10)

 

 

 

통과한 코드

 

import heapq
def solution(book_time):
    answer = 1
    # HH * 60 + MM로 변환
    book_time = [(int(s[:2])*60 + int(s[3:]), int(e[:2])*60 + int(e[3:])) for s, e in book_time]
    # 대실 시작 시간을 기준으로 정렬 
    book_time.sort(key=lambda x: x[0])

    heap = []
    for s, e in book_time:
        # 할당된 객실이 없으면 객실 할당
        if not heap:
            heapq.heappush(heap, e)
            continue
        # 현재 객실 중 가장 빠른 대실 종료 시각이 현재 대실 시작 시각보다 같거나 빠르면 해당 객실을 현재 손님에게 할당
        if heap[0] <= s:
            heapq.heappop(heap)
        # 현재 객실 중 가장 빠른 대실 종료 시각이 현재 대실 시작 시각보다 늦으면 새로운 객실 할당
        else:
            answer += 1
        # 대실 종료 시각 + 10분
        heapq.heappush(heap, e+10)

    return answer

 

 

• 대실 종료 시각이 가장 빠른 객실을 기준으로 할당할지 안 할지 구분
  • -> 최솟값을 빠르게 찾을 수 있는 heapq 이용
  • heapq.heappush(heap, 종료 시각)

 

 

• 과정 확인

book_time = [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]

"""
정렬된 book_time: [(850, 1160), (860, 920), (900, 1020), (1000, 1100), (1100, 1280)] 

현재 손님의 대실 시작 시각:850, 현재 손님의 대실 종료 시각:1160

현재 손님의 대실 시작 시각:860, 현재 손님의 대실 종료 시각:920
현재 객실 중 가장 빠른 대실 종료 시각: 1160
# 새로운 객실 할당
객실 수: 2
heap: [930, 1160] 

현재 손님의 대실 시작 시각:900, 현재 손님의 대실 종료 시각:1020
현재 객실 중 가장 빠른 대실 종료 시각: 930
# 새로운 객실 할당
객실 수: 3
heap: [930, 1160, 1030] 

현재 손님의 대실 시작 시각:1000, 현재 손님의 대실 종료 시각:1100
현재 객실 중 가장 빠른 대실 종료 시각: 930
# 해당 객실을 현재 손님에게 할당 

heap: [1030, 1160, 1110] 

현재 손님의 대실 시작 시각:1100, 현재 손님의 대실 종료 시각:1280
현재 객실 중 가장 빠른 대실 종료 시각: 1030
# 해당 객실을 현재 손님에게 할당 

heap: [1110, 1160, 1290] 
"""

 

 

 

 

 

참고)

 

https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Programmers-%ED%98%B8%ED%85%94-%EB%8C%80%EC%8B%A4-Python

[알고리즘] Programmers 호텔 대실 #Python

 

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기