[프로그래머스] LV.2 호텔 대실 / 파이썬(Python)

 

📜 문제 설명

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다.

한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 book_time이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ book_time의 길이 ≤ 1,000
  • book_time[i]는 ["HH:MM", "HH:MM"]의 형태로 이루어진 배열입니다
    • [대실 시작 시각, 대실 종료 시각] 형태입니다.
  • 시각은 HH:MM 형태로 24시간 표기법을 따르며, "00:00" 부터 "23:59" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

 

🔗 문제 링크

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

프로그래머스

 

💡 문제 풀이

처음에 했던 접근 - 15점

어떤 알고리즘을 적용할지 고민하다가 처음에는 탐욕법으로 풀어야겠다고 생각했다. 최대한 적은 수의 객실로 주어진 손님을 모두 받는 것이 목표이기 때문에 탐욕법으로 퇴실 시간을 기준으로 정렬한 다음 해당 객실에 최대한 많은 손님을 받고 받을 수 없었던 손님들도 다음 방에 최대한 우겨넣었다.

보기 좋게 틀렸다 🤣

풀이도 굉장히 지저분하다. 특히 두 손님이 같은 객실에 우겨넣어질 수 있는지 비교하는 부분에서 괜히 datetime 모듈을 썼는데 더 지저분해졌다. 15점인가 받고 나서 더 단순한 풀이법으로 풀었더니 풀렸다.

# 틀린 풀이
# 이렇게 풀지 마세요
import datetime

def calculate_time(start, end):
    start = start.split(":")
    end = end.split(":")
    
    now = datetime.datetime.now()

    s = datetime.datetime(now.year, now.month, now.day, int(start[0]), int(start[1]))
    e = datetime.datetime(now.year, now.month, now.day, int(end[0]), int(end[1]))
    
    if e + datetime.timedelta(minutes=-10) >= s:
        return True
    return False

def solution(book_time):
    answer = 0
    
    while book_time:
        book_time = sorted(book_time, key = lambda x : x[1])
        answer += 1
        now = book_time[0][1]
        book_time.pop(0)
        idx, length = 0, len(book_time)
        
        while idx < length:

            if calculate_time(now, book_time[0][0]):
                now = book_time[0][1]
                book_time.pop(0)
            
            else:
                book_time.append(book_time.pop(0))        
            idx += 1
        
    return answer

 

다시 단순하게 접근 - 100점

하루 24시간은 60분이니까 24 * 60 크기의 0 배열을 만든다. 총 1440의 크기이다. 

그리고 손님의 입실 시간과 퇴실 시간에 해당하는 인덱스에 1씩 더한다. 입실과 퇴실이 겹치는 경우 같은 방에 숙박할 수 없으므로 겹치는 시간대는 2가 되고 3명이 겹친다면 3이 된다.

모든 손님의 입실, 퇴실 시간을 확인하고 나면 배열에서 가장 큰 수가 필요한 방의 수이다.

# 단순한 풀이
# 모든 테케 통과
def solution(book_time):
    daytime = [0] * (24 * 60)
    
    for start, end in book_time:
        start = start.split(":")
        end = end.split(":")
        
        start = int(start[0]) * 60 + int(start[1])
        end = int(end[0]) * 60 + int(end[1]) + 10
        
        if end > 1440:
            end = 1440
        
        for i in range(start, end):
            daytime[i] += 1
    
    return max(daytime)