[프로그래머스] 호텔 대실 | 파이썬

---

문제설명

호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 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" 까지로 주어집니다.
    • 예약 시각이 자정을 넘어가는 경우는 없습니다.
    • 시작 시각은 항상 종료 시각보다 빠릅니다.

 

입출력 예

---

문제풀이

• 해당 문제는 주어지는 예약 시간표 배열의 길이가 1000이하이기 때문에 2중 for 문을 적용하여 시간복잡도 O(n^2)로 풀어도 시간 초과가 발생하지 않는다. 그래서 다양한 풀이가 가능하지만 나는 그리디 알고리즘으로 접근하여 풀었다.
• 그리디 알고리즘은 간략하게 설명하면 최종적인 결과물을 고려하지 않고 매 선택의 분기에서 가장 이득이 되는 선택을 하며 결과에 도달하는 알고리즘이다. (상세한 설명은 잘 정리된 링크를 공유한다. : https://velog.io/@kyunghwan1207/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm-%ED%83%90%EC%9A%95%EB%B2%95)
• 알고리즘을 적용하기 전에 전처리 과정이 필요하다. 우선 예약 테이블이 주어지는 형식이 ["시간:분"]의 문자열 형태로 주어지기 때문에 앞으로 계산의 편리성을 위하여 분단위의 정수형으로 변환시켜준다. 그리고 예약 시간들을 시작 시간을 기준으로 오름차순으로 정렬한다.
• 마지막으로 예약을 받기 시작하는데 첫 예약에서 rooms가 비었기 때문에 바로 추가해주고 그 이후부터는 기존의 방들을 for문으로 확인하면서 예약이 가능하다면 기존의 방에 추가를하고 모든 방에 예약이 불가능하면 새로운 방을 생성하여 예약을 받아준다. 그리고 모든 예약을 확인 한 후에 생성된 방의 수를 구하여 반환해 주면 된다.
• 다른 사람들의 풀이는 확인해 보니 그리디 알고리즘 말고도 다른 방식으로도 풀이가 가능했다. 다음 포스트에 다른 방식으로 풀어서 같은 결과를 낼 수 있는지 포스트 해보도록 하겠다.

코드 & 설명

def solution(book_time):
    def hourToMin(str_time):
        return int(str_time[0:2]) * 60 + int(str_time[3:])
    
    book_times = sorted([[hourToMin(i[0]), hourToMin(i[1]) + 10] for i in book_time])
    rooms = []
    for book_time in book_times:
        if not rooms:
            rooms.append(book_time)
            continue
        for index, room in enumerate(rooms):
            if book_time[0] >= room[-1]:
                rooms[index] = room + book_time
                break
        else:
            rooms.append(book_time)
    return len(rooms)