[프로그래머스][Heap] 호텔 대실

호텔 대실

프로그래머스

 

 

• 내 풀이
  • 처음에 요격 시스템이랑 유사한 문제라고 생각하고 끝지점으로 정렬 해버림
  • 하지만, 요격 시스템이 여러팀을 한번에 처리하는 방식이라면,
  • 이번 문제는 각 호텔 방마다 1개의 팀만 가능하기 때문에 아예 다른 문제임
    • "겹치지 않도록 배정하는 문제" → 시작 시간 기준 정렬
    • "덮거나 포함시키는 문제" → 끝나는 지점 기준 정렬
  • heap을 이용해서 시작시간이 가장 빠른 방을 찾고
  • 가지고 있는 객실 중에 가장 빨리 끝난 방과 시작시간을 비교하면서
  • 방을 늘릴지, 해당 방을 쓸지 결정

 

import heapq

def solution(book_time):
    time=[]
    for bk in book_time:
        sh,sm=map(int,bk[0].split(":"))
        eh,em=map(int,bk[1].split(":"))
        heapq.heappush(time, (sh*60+sm,eh*60+em))
        
    result=[]
    heapq.heappush(result,0)
    cnt=1
    while time:
        s,e=heapq.heappop(time)
        
        x=heapq.heappop(result)
        if x<=s:
            heapq.heappush(result,e+10)
        else:
            heapq.heappush(result,x)
            cnt+=1
            heapq.heappush(result,e+10)
            
    return cnt