📗 호텔 대실

프로그래머스

def convert_time(time):
    h, m = map(int, time.split(':'))
    return h * 60 + m

def cal_time(time):
    total_m = convert_time(time)
    total_m += 10
    h, m = divmod(total_m, 60)
    return f'{str(h).zfill(2)}:{str(m).zfill(2)}'

def solution(book_time):
    answer, rooms = 0, 0
    l = len(book_time)
    timeline = []
    
    for start, end in book_time:
        timeline.append((convert_time(start), 1))
        timeline.append((convert_time(cal_time(end)), -1))
        
    timeline.sort()
    
    for _, check in timeline:
        rooms += check
        answer = max(answer, rooms)
    
    return answer

• 대표적인 그리디 유형의 문제인 장소 배정 문제, 그 중에서도 프로그래머스의 '호텔 배정' 문제입니다.

왜 이렇게 풀었을까?

• 사실 timeline의 문자열들(체크인, 체크아웃 시간)을 바로 정렬하여 문제를 풀 수도 있었지만, 문제에서 '예약 시각이 자정을 넘어가는 경우'가 없었기에 시간을 분 단위로 변환하여 푸는 방법을 택하게 되었습니다.
• 처음 timeline을 정의할 때 체크인을 한 행위는 객실의 수를 1로, 체크아웃을 한 행위는 객실의 수를 -1로 설정하여 추후 누적합으로 전체 객실 수를 계산할 때 사용하였습니다.
• 처음에는 모든 예약들에 대해 for문을 돌리며 객실 수를 파악했었는데, 그러다 보니 시간 복잡도가 증가하는 것을 확인하게 되어 조금 더 효율적인 방법을 고안하다가 생각해낸 것이 누적합이었습니다.
• 조건이 필요없이 그리디와 단순 사칙 연산만 사용하여 O(1)의 시간 복잡도로 객실 수를 파악할 수 있었습니다.
• 나중에 기회가 되면 힙(Heap) 자료구조를 활용하여 조금 더 효율적으로 풀어볼 예정입니다 !!