호텔 대실

호텔 대실

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

문제

풀이(그리디)

내가 생각한 전반적인 로직은 book_time을 오름차순 정렬을 하고나면 book_time[0]은 현재 가장 일찍 시작하는 시간이 될 것이다. 그리고 book_time[0]을 pop하고 이것을 기준으로 Room을 만드는 것이다. 만족하는 시간이 있다면 그것을 pop해준다. 이렇게 가장 최선인 방법으로 하나의 Room을 찾고나서 더 이상 만들 수 없다면 두 번째 Room을 만들어준다. book_time[0]은 현재 가장 일찍 시작하는 시간이므로 또한 이것을 기준으로 두 번째 Room을 만들어 주는 것이다. 이렇게 book_time이 비어있다면 그 때 종료한다.

1. book_time을 오름차순 정렬을 한다.
   

2. 문자열 시간을 계산하기 쉽도록 분으로 바꾸는 함수를 만든다. ("09:10" => 550)
   

3. 로직을 구현한다.
   

def solution(book_time):
    book_time.sort(key = lambda x:(x[0]))
    
    def get_minute(time):
        tmp = time.split(":")
        hour, minute = int(tmp[0]), int(tmp[1])       
        return hour*60 + minute
          

    answer = 0
    while book_time:
        cur_end, pointer = get_minute(book_time[0][1]), 0 ## cur_end => book_time에서 가장 일찍 시작하는 시간 
                                                          ## cur_end 기준으로 Room을 만들기
        book_time.pop(pointer)
        
        while True:                                       ## Room 만들기 시작
            if pointer == len(book_time):                 ## 종료조건
                break
            new_start, new_end = get_minute(book_time[pointer][0]), get_minute(book_time[pointer][1])
            if cur_end + 10 <= new_start:                 ## 10분 청소시간을 더한 시간보다 더 크다면 해당 Room에 포함
                cur_end = new_end              
                book_time.pop(pointer)
            else:                                         ## 조건에 만족하지 않으면 pointer를 1 증가
                pointer += 1             
        answer = answer + 1                               ## 하나의 Room 만들었으므로 answer을 1 증가

    return answer

결과(그리디)