호텔 대실

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

 

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

 

첫 번째 손님이 10시 10분에 퇴실하고 10분간 청소를 하면 10시 20분에는 입실할 수가 없다. 
0.000000.....1초라도 일찍 퇴실하거나 뒷 손님이 0.000000000... 1초라도 늦게 입실해야 방 하나로 가능... 

어쨌든 건 풀자... 

 

딕셔너리로 풀어보았다. 

def solution(bookings):
    def booking2time(booking, is_end=False):
        return int(booking[:2]) * 60 + int(booking[3:]) + (10 if is_end else 0)

    from collections import defaultdict
    table = defaultdict(int)
    for start, end in bookings:
        table[booking2time(start, False)] += 1
        table[booking2time(end, True)] -= 1
    max_rooms = temp_rooms = 0
    for time in sorted(table.keys()):
        temp_rooms += table[time]
        max_rooms = max(max_rooms, temp_rooms)
    return max_rooms

예약이 시작되면 필요한 방이 하나씩 증가하고, 예약이 종료되면 하나씩 감소한다.  
예약 시작 시간과 '종료 + 청소' 시간을 체크한 뒤,
순서대로 더해주면서 최댓값을 찾으면 된다. 

테스트 1 〉	통과 (0.06ms, 10.3MB)
테스트 2 〉	통과 (0.39ms, 10.4MB)
테스트 3 〉	통과 (1.55ms, 10.6MB)
테스트 4 〉	통과 (0.95ms, 10.5MB)
테스트 5 〉	통과 (0.03ms, 10.4MB)
테스트 6 〉	통과 (2.49ms, 10.7MB)
테스트 7 〉	통과 (2.47ms, 10.5MB)
테스트 8 〉	통과 (0.70ms, 10.5MB)
테스트 9 〉	통과 (0.50ms, 10.4MB)
테스트 10 〉	통과 (1.97ms, 10.5MB)
테스트 11 〉	통과 (3.07ms, 10.7MB)
테스트 12 〉	통과 (2.70ms, 10.5MB)
테스트 13 〉	통과 (0.55ms, 10.2MB)
테스트 14 〉	통과 (1.22ms, 10.6MB)
테스트 15 〉	통과 (2.29ms, 10.5MB)
테스트 16 〉	통과 (0.66ms, 10.5MB)
테스트 17 〉	통과 (1.43ms, 10.6MB)
테스트 18 〉	통과 (1.86ms, 10.5MB)
테스트 19 〉	통과 (1.13ms, 10.4MB)

 

힙큐(우선순위 큐)로도 풀 수가 있다. 

def solution(bookings):
    def booking2time(booking):
        return int(booking[:2]) * 60 + int(booking[3:])

    from heapq import heapreplace, heappush
    queue = [0]
    for start, end in sorted(bookings):
        start_time, end_time = booking2time(start), booking2time(end)
        if queue[0] <= start_time:
            heapreplace(queue, end_time + 10)
        else:
            heappush(queue, end_time + 10)
    return len(queue)

입실 시간 순서대로 입장한다.
큐에는 '퇴실+청소' 시간을 넣어준다. 

여기서 약간의 트릭을 사용한다. 

앞 방의 가장 빠른 '퇴실+청소'시간이
입실 시간보다 빠르면
'하나만' 빼준다. 

여기서 남는 방이 생길 수 있다.
이것들이 모이면 필요한 방의 최댓값이 된다. 

테스트 1 〉	통과 (0.04ms, 10.3MB)
테스트 2 〉	통과 (0.26ms, 10.3MB)
테스트 3 〉	통과 (1.19ms, 10.5MB)
테스트 4 〉	통과 (0.65ms, 10.5MB)
테스트 5 〉	통과 (0.02ms, 10.4MB)
테스트 6 〉	통과 (1.21ms, 10.4MB)
테스트 7 〉	통과 (1.11ms, 10.5MB)
테스트 8 〉	통과 (0.47ms, 10.4MB)
테스트 9 〉	통과 (0.31ms, 10.4MB)
테스트 10 〉	통과 (1.07ms, 10.6MB)
테스트 11 〉	통과 (1.50ms, 10.6MB)
테스트 12 〉	통과 (1.24ms, 10.5MB)
테스트 13 〉	통과 (0.40ms, 10.4MB)
테스트 14 〉	통과 (1.02ms, 10.5MB)
테스트 15 〉	통과 (1.17ms, 10.5MB)
테스트 16 〉	통과 (0.44ms, 10.4MB)
테스트 17 〉	통과 (1.27ms, 10.6MB)
테스트 18 〉	통과 (0.84ms, 10.4MB)
테스트 19 〉	통과 (1.14ms, 10.5MB)

 

순수한 마음으로 풀어도 좋다.
분단위로 모든 시간을 확인한다. 
일종의 시뮬레이션이다. 

여기서도 문제의 모순을 찾을 수 있다. 

def solution(bookings):
    def booking2time(booking):
        return int(booking[:2]) * 60 + int(booking[3:])

    table = [0] * (24 * 60 + 10)
    for start, end in bookings:
        start_time, end_time = booking2time(start), booking2time(end)
        for index in range(start_time, end_time + 10):
            table[index] += 1
    return max(table)

테스트 1 〉	통과 (0.09ms, 10.5MB)
테스트 2 〉	통과 (5.98ms, 10.3MB)
테스트 3 〉	통과 (48.02ms, 10.5MB)
테스트 4 〉	통과 (13.48ms, 10.4MB)
테스트 5 〉	통과 (0.11ms, 10.4MB)
테스트 6 〉	통과 (22.06ms, 10.5MB)
테스트 7 〉	통과 (23.15ms, 10.4MB)
테스트 8 〉	통과 (9.62ms, 10.4MB)
테스트 9 〉	통과 (7.80ms, 10.4MB)
테스트 10 〉	통과 (18.35ms, 10.3MB)
테스트 11 〉	통과 (30.78ms, 10.5MB)
테스트 12 〉	통과 (50.33ms, 10.4MB)
테스트 13 〉	통과 (2.58ms, 10.2MB)
테스트 14 〉	통과 (19.74ms, 10.5MB)
테스트 15 〉	통과 (24.77ms, 10.4MB)
테스트 16 〉	통과 (5.74ms, 10.4MB)
테스트 17 〉	통과 (21.00ms, 10.6MB)
테스트 18 〉	통과 (9.97ms, 10.4MB)
테스트 19 〉	통과 (6.77ms, 10.5MB)