알고리즘 코드카타 115 - 호텔 대실

https://school.programmers.co.kr/learn/courses/30/lessons/155651/solution_groups?language=python3

프로그래머스

 

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

 

오랜만에 풀어보는 알고리즘 코드카타, 114 번 문제는 거의 풀어냈지만 아직 배우지 않은 부분이라서 일단 넘어갔다.

이번에도 굳이 굳이 말하면 당연히 놀았던 것은 아니고 백준 등, 다른 사이트에 있는 문제 위주로 풀었다.

 

문제는 호텔의 예상 현황을 보고 필요한 최소객실의 수를 구하는 것이다. 즉, 예약목록의 각 시간들이 중첩되는 횟수중 가장 많은 것을 구하면 된다.

def solution(book_time):
    time_line = [0]*24*60 + [0]*10
        
    return max(time_line)

 

먼저 24시간을 1분단위로 나눠서 리스트를 작성한다. 그리고 book_time의 각 예약목록을 분단위로 쪼개서 예약중인 시간에 time_line에 반영하여 더해줄 예정이다. 따라서 예약이 중첩되는 만큼 time_line의 최댓값이 상승하게 되고 필요한 방의 수는 time_line의 최댓값이 된다. 뒤에 10을 추가해준 이유는 퇴실후 청소시간을구할 때, 오류가 발생하지 않도록 하기 위함이다.

 

# def solution(book_time):
    # time_line = [0]*24*60 + [0]*10
    for book in book_time:
        start = int(book[0][:2])*60 + int(book[0][-2:])
        end = int(book[1][:2])*60 + int(book[1][-2:])
        
    # return max(time_line)

 

book_time을 숫자형태로 바꿔준다. 시간부분은 60을 곱해서 분으로 만들어주고 분은 그대로 더해서 입실시간과 퇴실시간을 분으로 치환해준다.

 

# def solution(book_time):
    # time_line = [0]*24*60 + [0]*10
    # for book in book_time:
        # start = int(book[0][:2])*60 + int(book[0][-2:])
        # end = int(book[1][:2])*60 + int(book[1][-2:])
        for i in range(start, end+10):
            time_line[i] += 1
        
    # return max(time_line)

 

마지막으로 입실시간부터 퇴실시간 까지의 범위에 모두 1을 더해주면 완료.

같은 시간에 다른 손님이 온다면 해당 시간의 숫자가 계속해서 늘어나므로 필요한 방의 수를 구할 수 있다.

완료!

 

운이 좋게도 누적합으로 계산하는 방법이 금방 떠올라서 쉽게 풀렸던 문제였다.