1. 문제 해석
예약 시간을 담은 리스트를 주고, 최소한의 방을 사용하여 겹치지 않게 고객들에게 방을 내어준다.
사용한 방은 청소시간 10분을 가져야 한다.
위에 1번 예시를 살펴보면, 아래처럼 3개의 방을 사용하여 배정할 수 있다.
2. 문제 접근
book_time의 범위가 (1 ≤ N ≤ 1,000)이 주어졌고, 적은 범위이기에 DP나 브루트 포스 혹은 오래 걸리는 알고리즘까지 생각할 수 있다. 문제는 각 예약에 맞는 방을 배정하면서 겹치지 않는 또 하나의 루프를 생각해야 하는 것으로 보였다. O(N^2)까지 가능한 범위이기에 그리디을 사용했다.
3. 알고리즘 풀이
먼저 주어진 book_time을 int로 바꿔줬다.
for i in book_time:
for j in range(2):
h,m=i[j].split(":") # 시간 문자열을 시간과 분으로 분리
i[j]=int(h)*60+int(m) # 시간과 분을 분 단위로 변환그리고서 생각할 수 있는 방법은
1. 먼저 방이 아예 없으면 새로운 방을 만들어서 배정한다
2. 방이 있으면 사용 가능 한지 확인한 뒤, 가능하면 배정한다.
3. 사용 가능한 방도 없다면 추가적인 방을 새로 만들어야 한다.
최종 제출 코드
def solution(book_time):
for i in book_time:
for j in range(2):
h,m=i[j].split(":")
i[j]=int(h)*60+int(m)
book_time.sort() # 예약 시간을 시작 시간에 따라 정렬
rooms=[] # 방 리스트
for book in book_time:
if not rooms: # 맨 처음, 방이 없다면
rooms.append(book) # 방을 만들어줌
continue
# 생성 된 각 방을 돔
for index, room in enumerate(rooms):
# 대실 시작 시각 >= 퇴실 시간 + 청소시간 10분
if book[0] >= room[1]+10:
rooms [index] = book # 새로운 예약으로 갱신
break
else: # 방은 있는데 사용 불가능하다면 방 추가
rooms.append(book)
return len(rooms)이 코드에서는 조심해야 할 점이 if- else를 쓴게 아니라, for - else 문을 이용했다.
이는 for 루프에서 찾으려는 조건이 충족되지 않았을 때의 대안적인 동작을 제공한다.
for - else는 해당 게시물 끝 부분에도 정리해 놓았다.
(2) heap을 이용한 풀이
from heapq import heappop, heappush
def solution(book_time):
rooms = []
book_time.sort(key = lambda _:_[0])
for book in book_time :
check_in = num(book[0])
check_out = num(book[1]) + 10
if len(rooms) != 0 and rooms[0] <= check_in :
heappop(rooms)
heappush(rooms,check_out)
return len(rooms)
사실 이 코드를 소개해보고 싶어서 글을 썼다.
heap을 이용한 알고리즘인데, 실행 결과 속도가 압도적으로 빠르다.
앞에 흐름까진 동일하고, 뒤에 방이 존재하고 사용 가능할 때 heappop그리고 heappush를 해주는 점이 다르다..
회고
heap알고리즘은 생각도 못 했기에 소개하고자 글을 썼다.
해당 문제처럼 예약, 대기 시간 문제에서 자주 heap이 쓰이는 것은 알고 있었지만, 아직 응용 능력이 부족하여 이를 활용하지 못했다.
Heap 알고리즘은 우선순위 큐를 구현하는데 매우 유용하다. 이를 통해 데이터의 삽입, 삭제, 최솟값 또는 최댓값에 대한 조회를 빠르게 수행할 수 있다. 특히 예약 및 대기 시간과 같은 문제에서는 우선순위에 따라 데이터를 관리하는 것이 중요함을 느꼈다.
heap 개념에 대해서는 아래 두 게시물에서 다뤘었다.
1. heap 알고리즘 문제 회고
2. heappush만 가능할까
이렇게 수행시간이 차이가 날 줄은 몰랐다. 앞으로는 문제 해결에 Heap을 고려하여 보다 효율적인 알고리즘을 구현해보고자 한다.
