[프로그래머스 - lv2] 호텔 대실 / 파이썬

 

 

문제 링크 :  https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

 

---

문제 풀이)

시간을 분으로 바꿔 생각하는게 핵심인 문제였던 것 같다.

[입실 시간, 퇴실 시간]  HH:MM 포맷으로 적혀있는 시간을 분으로 환산하면 문제가 생각보다 간단해진다.

 

시간을 분으로 환산하기 위해 다음과 같은 함수를 구현했다.

def convert_minute(start, end):
    start = int(start[:2]) * 60 + int(start[-2:])
    end = int(end[:2]) * 60 + int(end[-2:])
    return (start, end)

위 함수를 이용하여 입실 퇴실 시간을 분으로 환산에 주어진 book_time_table을 업데이트 시킨다.

그 다음 입실 시간 기준으로 book_time_table을 정렬시킨다. 

 

다음으로 heapq라는 자료구조를 이용해 문제를 해결했다. 종료시간을 기준으로 heap에 자료를 삽입한다. 이렇게 하면 힙의 최상단 노드는 항상 종료시간이 제일 빠른순으로 자동 정렬 되어있다,

 

그 다음 가장 빠른 시간 기준으로 heap의 종료 시간과 다음과 같은 비교를 한다.

1) 만약 힙의 최상단 노드(즉 가장 빠른 종료 시간)이 입실 시간보다 빠르다면 기존 객실을 할당해 주면 된다.

2) 만약 그렇지 않다면 새로운 방을 할당해 주면 된다.

 

전체 코드는 다음과 같다.

def convert_minute(start, end):
    start = int(start[:2]) * 60 + int(start[-2:])
    end = int(end[:2]) * 60 + int(end[-2:])
    return (start, end)
    
def solution(book_time):
    answer = 1
    for idx, item in enumerate(book_time):
        book_time[idx] = convert_minute(item[0], item[1]) # 분으로 환산한 시각으로 list update
    book_time.sort() # 입실 시각 기준 정렬
    heap = []
    for s, e, in book_time:
        if not heap: # 최초 수행시 힙에 자료 삽입
            heapq.heappush(heap, e+10)
            continue
        if heap[0] <= s: # 현제 가장 빠른 퇴실 시각이 입실 시각보다 빠르다면 기존방 할당
            heapq.heappop(heap)
        else:
            answer += 1 # 그렇지 않다면 새로운방 할당
        heapq.heappush(heap, e+10) # 퇴실 시각 기준 10분 청소후 할당
    return answer

 

다른 풀이)

def solution(book_time):
    dic = {}
    for book in book_time:
        st = time2val(book[0])
        en = time2val(book[1])
        for t in range(st,en+10):
            if dic.get(t) == None:
                dic[t] = 1
            else:
                dic[t] += 1
    
    return max(dic.values())

위에서 처럼 입실 퇴실 시각을 분단위로 바꾼것은 동일했다.

하지만 book_time 테이블을 돌면서 dict를 이용해 분단위로 겹치는 부분중에 가장 큰값을 return 해 주는 방식으로도 해결할 수 있었다.