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

 

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

프로그래머스

이 문제는 두 가지로 풀이 가능합니다.

 

1. Python의 datetime과 같은 시간 관련 모듈을 이용해서 푸는 것

2. 모든 시간을 분으로 환산하여 table을 만든 다음, 시작 시간과 종료 시간을 기록하고 부분합으로 푸는 것

 

제한 사항에서 명시하는 범위가 작기 때문에 어느 쪽으로도 풀이가 가능합니다.

datetime과 같은 시간 관련 모듈을 이용하여 정석적으로 풀고 싶은 경우 첫 번째 풀이를, 최대한 시간 효율성이 높게 풀고 싶은 경우 두 번째 풀이를 채택하면 되겠습니다.

나의 풀이

from datetime import datetime, timedelta


def solution(book_time):
    timetable_in_datetime: list = []  # datetime으로 변환된 대실 타임테이블
    rooms_in_use: list = []  # 현재 사용중인 방
    rooms_required: int = 0  # 필요한 방의 수

    for book in book_time:
        book_start: tuple = tuple(map(int, book[0].split(":")))  # 대실 시작 시간
        book_end: tuple = tuple(map(int, book[1].split(":")))  # 대실 종료 시간
        book_start_datetime: datetime = datetime(2000, 1, 1, book_start[0], book_start[1])
        book_end_datetime: datetime = datetime(2000, 1, 1, book_end[0], book_end[1]) + timedelta(minutes=10)

        # 대실 시간표에 삽입
        timetable_in_datetime.append([book_start_datetime, book_end_datetime])

    # 시작 시간, 종료 시간이 빠른 순서대로 정렬
    timetable_in_datetime_sorted: list = sorted(sorted(timetable_in_datetime, key=lambda x: x[1]), key=lambda x: x[0])

    # 대실 시간표 선형 탐색
    for book in timetable_in_datetime_sorted:
        rooms_in_use.append(book[1])  # 사용중인 방 목록에 현재 손님 추가
        rooms_in_use.sort()  # 다 사용된 방 걸러내기 위해 정렬
        while rooms_in_use[0] <= book[0]:  # 이미 사용이 끝난 방이면
            rooms_in_use.pop(0)  # 사용중인 방 목록에서 제거
        rooms_required = max(rooms_required, len(rooms_in_use))  # 필요한 방의 수 갱신

    return rooms_required

효율적인 풀이

def solution(book_time):
    time_table = [0 for _ in range(60 * 24)]
    for start, end in book_time:
        start_minutes = 60 * int(start[:2]) + int(start[3:])
        end_minutes = 60 * int(end[:2]) + int(end[3:]) + 10

        if end_minutes > 60 * 24 - 1:
            end_minutes = 60 * 24 - 1

        time_table[start_minutes] += 1
        time_table[end_minutes] -= 1

    rooms_required : int = 0
    rooms_current_count : int = 0
    for i in time_table:
        rooms_current_count += i
        rooms_required = max(rooms_required, rooms_current_count)

    return rooms_required