Py) 프로그래머스 155651

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

프로그래머스

 

0. 입출력

 

1. Solution

1-1. 사용 자료구조 및 알고리즘: heap

1-2. 로직

1) 초 단위로 시간을 모두 정리해 들어온 초, 나가는 초를 오름차순으로 정리하고
2) 처음 손님의 퇴실 시간을 heap에 넣어준다.
3) min heap이므로 가장 빨리 나가는 손님이 정렬될 것이고, list에서 가장 먼저 들어오는 손님의 시간과 비교가 가능하다
   3-1) 다음 손님의 입실 시간이 이전 손님의 퇴실 시간보다 작다면 방이 더 없으므로 answer += 1해주고
   3-2) 더 크다면 상관이 없으므로, heap에 10분을 추가(퇴실시간 + 청소시간)해서 넣어준다.
4) 손님 수 만큼 반복

1-3. 코드

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]))
    # lambda - 정렬 1순위 x[0], 2순위 x[1]
    
    for i in range(len(book_time_minute)):
        if not heap:
            heapq.heappush(heap, book_time_minute[i][1]+10)   # +10
        else:
            available_time = heapq.heappop(heap)
            if available_time > book_time_minute[i][0]:    # 들어오는 시간보다 가능 시간이 더 크다면
                answer += 1
                heapq.heappush(heap, available_time)
            heapq.heappush(heap, book_time_minute[i][1]+10)
            
    return answer



book_time = [["15:00", "17:00"], ["16:40", "18:20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]]
print(solution(book_time))

 

1-4. 피드백

#1

if not heap을 if i not in heap으로 생각함 ㅎ

#2

sorted(book_time_minute, key = lambda x: (x[0], x[1]))      -> x[0]을 기준으로 정렬하고, x[0]으로 우열을 가릴 수 없을 때 x[1]로 비교