호텔 대실 - Pyton, 구현, 누적합, 스위핑(Sweeping), 힙(heap)

 

 

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

프로그래머스

 

 

코드 & 풀이

 

def solution(book_time):
    time_changes = [0] * (60 * 24 + 1)  # 각 분에서의 시간 변화 기록

    for start, end in book_time:
        checkin_time = 60 * int(start[:2]) + int(start[3:])
        checkout_time = 60 * int(end[:2]) + int(end[3:]) + 10

        if checkout_time > 60 * 24:
            checkout_time = 60 * 24

        time_changes[checkin_time] += 1
        time_changes[checkout_time] -= 1

    # 최대 방 개수 계산
    max_rooms = 0
    current_rooms = 0
    for change in time_changes:
        current_rooms += change
        max_rooms = max(max_rooms, current_rooms)

    return max_rooms

 

누적합을 사용하는 방법입니다.

 

하루를 분 단위로 한만큼을 -1 (23:59까지니까)해서 리스트에 초기화하고

 

체크인 시간은 +1을,

 

체크아웃 시간은 -1을 해줍니다.

 

+1, -1의 의미는

 

그 시간대에 방이 필요하다, 필요없다 라는 의미입니다.

 

예약을 모두 체크하면

 

time_chages를 돌면서 가장 방이 많이 필요했던 순간을 찾습니다.(누적합)

 

누적 계산 및 최대값 추적

1. current_rooms는 방의 개수를 누적합니다.
2. 매 반복마다 current_rooms를 업데이트하고, 그 값이 max_rooms보다 크면 max_rooms를 갱신합니다.

시간	변화량	current_rooms	max_rooms
14:10	+1	1	1
15:00	+1	2	2
16:40	+1	3	3
17:00	-1	2	3
18:20	-1	1	3
19:20	-1	0	3

 

최종적으로 max_rooms = 3이 됩니다.

 

 

import heapq

def solution(book_time):
    book_time = sorted(book_time, key=lambda x: (x[0], x[1]))
    room = []
    for start, end in book_time:
        checkin_time = 60 * int(start[:2]) + int(start[3:])
        checkout_time = 60 * int(end[:2]) + int(end[3:]) + 10

        # 기존 방에서 배정 가능한지 확인
        if room and room[0] <= checkin_time:
            heapq.heappop(room)  # 가장 빨리 비는 방 업데이트

        # 새 예약 추가
        heapq.heappush(room, checkout_time)

    return len(room)

 

힙을 사용한 방법입니다.

 

가장 먼저 체크인 시간을 기준으로 정렬을 해줘야 합니다.

 

그 후에

 

가장 빨리 비는 방을 찾고,

 

그 방에 입장이 가능하다면

 

기존의 가장 빨리 비는 방을 처리하고, 새 예약을 추가해줍니다.

 

그렇게 모든 예약을 처리 한 후

 

방의 개수를 세면 원하는 결과를 얻을 수 있습니다.

 

 

 

다음에 또 봐요