문제

링크

Code

from collections import deque


def convertor(time:str):
    time = time.split(":")
    return (int(time[0]) * 60) + int(time[1])


def solution(book_time):
    room_time = []
    for time in book_time:
        start_time, end_time = convertor(time[0]), convertor(time[1]) + 10
        room_time.append([start_time, end_time])

    rooms = []
    rooms.append([0]*(24*60+10))
    room_time.sort()
    
    for start, end in room_time:
        room_assigned = False
        for room in rooms:
            if all(element == 0 for element in room[start:end]):
                room[start:end] = [1] * (end - start)
                room_assigned = True
                break
        
        if not room_assigned:
            new_room = [0] * (24 * 60)
            new_room[start:end] = [1] * (end - start)
            rooms.append(new_room)
    
    
    return len(rooms)

고찰

1. 문제는 곧이곧대로 풀거나, 수학적인 공식을 통해서 단번에 풀어낼 수 있다.
   • 여기선 호텔을 정말 빌리는 행위를 실제 세계와 대응해서 구현하거나
   • flag나, 각 시간대마다 겹치는 시간대의 개수를 세거나
   • 위와 같이 구현할 수 있다.
   • 그러나 실제로 선택한 것은 호텔에서 시간대만큼 직접 빌리는 행위를 구현하였다.
   • 이 방법의 장점은 문제 해결을 위한 알고리즘을 생각해내지 않아도 된다는 점이다.
2. 입력값을 정렬하자.
   • 먼저 온 손님을 먼저 처리해야 한다.
   • 만약 이 순서를 지키지 않아도 된다고 한다면, 아래와 같은 상황을 염두해볼 수 있다.
   • 빌린 시간이 짧은 순으로 정렬 -> 프로세스 스케줄링 기법에서 따온 생각이다.

다른 사람의 풀이

누적합으로 풀면 아주 쉽다 !!