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

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

🔎호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 "book_time" 이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

출처: 프로그래머스

---

오랜만에 난이도 순으로 풀지 않고 최신순으로 정렬해서 풀었는데, 이 문제가 처음에 있었고 정답률이 30퍼대라 잔뜩 긴장한 채로 문제에 들어갔다.

 

읽어보니 전에 카카오였는지 그냥 프로그래머스 문제였는지에서 주차 입출 관련 문제가 있었는데 이 문제랑 비슷했던 것 같다.

 

다행히 오늘은 머리가 좀 잘 돌아가는지 문제를 보자마자 Priority Queue를 사용해야겠다는 생각이 들었고, 정답으로 이어질 수 있었다.

 

<정답 코드>

from queue import PriorityQueue
import datetime as dt


def solution(book_time):
    room = PriorityQueue()
    book_time = sorted(book_time)

    for start, end in book_time:
        if not room.qsize():
            room.put((end, start))
            continue

        out = room.get()
        clean = dt.datetime.strptime(out[0], '%H:%M') + dt.timedelta(minutes=10)
        if clean > dt.datetime.strptime(start, '%H:%M'):
            room.put(out)

        room.put((end, start))

    return room.qsize()

접근은 아래와 같다.

1.  book_time을 입장시간 기준으로 정렬한다. (예약이 뒤죽박죽으로 되어있기 때문에 필수 과정이다.)
2. 정렬된 book_time을 순회하면서 Priority Queue에 삽입한다.
   1. 삽입할 때는 퇴실이 빠른 기준으로 삽입한다.
   2. 가장 빨리 퇴실하는 [0]번째 방 + 10분이 현재 고객의 입장 시간보다 이른지 비교하는 과정을 포함한다.
3. get되지 못한 방들은 계속 이용되고 있다고 가정하면 Priority Queue의 길이가 정답이 된다.

 

정답을 도출하기 까지 총 두번의 시행착오가 있었다.

 

처음은 시간계산을 포함하지 않고 진행해서 틀렸었다.

시간이 문자열로 주어져있기 때문에 시간으로 전환하여 10분 뒤를 계산해줘야한다. (datetime 모듈)

 

두번째는 sort하지 않아서 틀렸었다.

Priority Queue를 채울 때 입장이 빠른 기준으로 처리해야하기 때문에 정렬을 해야했다.

 

이제 좁은 시각으로 문제를 바라보지 않고 좀 생각하는 시간을 가지게 된게 뿌듯했다.

앞으로도 이렇게 술술 문제가 풀렸으면 좋겠다.