[프로그래머스 Lv. 2] 호텔 대실

DaeHoon·2023년 2월 11일
0

프로그래머스

목록 보기
14/16

문제

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

접근

탐욕법으로 접근.

1) 시간을 분 단위로 만들어 리스트에 넣어준 뒤 시작 기준으로 정렬한다.
2) 이 후 for문을 돌리는데, 이 때 객실 추가여부를 확인하기 위해 대실이 끝나는 시간 + 10을 Min heap에 넣는다.
3) 대실이 끝나는 시간의 가장 작은 값(Min Heap에서 pop하면 나오는 값) 현재 인덱스의 시작 값과 비교하여 대실이 끝나는 시간이 더 큰 경우에 다시 힙에 넣고 answer를 증가시킨다.

Code

import heapq

def solution(book_time):
    def change_minute(time):
        t, m = map(int, time.split(":"))
        return t * 60 + m
    
    answer = 1
    book_time_minute = []
    heap = []
    for a,b in book_time:
        book_time_minute.append((change_minute(a), change_minute(b)))
    book_time_minute = sorted(book_time_minute, key=lambda x: (x[0],x[1]))
    
    for i in range(0, len(book_time_minute)):
        if not heap:
            heapq.heappush(heap, book_time_minute[i][1])
        else:
            available_time = heapq.heappop(heap)
            if (available_time > book_time_minute[i][0]):
                heapq.heappush(heap, available_time)
                answer+=1
            heapq.heappush(heap, book_time_minute[i][1]+10)
    
    return answer
profile
평범한 백엔드 개발자

0개의 댓글