[프로그래머스] 호텔 대실 LV2 by 파이썬 (python)

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

프로그래머스

 

문제 이해

1. 최소한의 객실만을 사용하여 예약손님 받기

2. 퇴실 기준 10분이후에 다음 손님 사용 가능

3. 00:00 ~ 23:59

 

접근법

1. heapq를 사용하여 객실의 끝나는 시간을 저장하기

2. 가장 빨리 끝나는 시간과 다음 이용자의 시작 시간을 비교

3. 다음 이용자의 시작시간이 더 느리다면 같은 객실을 이용 가능한 것 => heappop으로 앞의 시간 제거

4. 마지막에 heapq에 들어있는 갯수가 필요한 방의 갯수

 

 

코드

import heapq
def solution(book_time):
    book_time = sorted(book_time)
    rooms = []
    for s, e in book_time:
        if rooms and rooms[0] <= s:
            heapq.heappop(rooms)
        x = (e.split(":"))
        x[1] = int(x[1]) + 10
        x[0] = int(x[0])
        
        if x[1] >= 60:
            x[1] -= 60
            x[0] = x[0] + 1
        if x[0] > 24:
            x[0] -= 24
        
        if x[0] < 10:
            x[0] = "0" + str(x[0])
        if x[1] <10:
            x[1] = "0" + str(x[1])
        
        newe = str(x[0])+ ":" + str(x[1])
        heapq.heappush(rooms, newe)
        
    return len(rooms)

---

heapq?

- 이진 트리 기반의 최소 힙 자료구조를 제공한다. 

- 항상 정렬된 상태로 추가되고 삭제되며 min heap에서 가장 작은 값은 언제나 인덱스 0인 이진트리의 루트에 위치한다.

 

사용법

import heapq

//추가
heapq.heappush(배열, 값)
//삭제
heapq.heqpppop()