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

사용 언어: Python3

문제

호텔 대실

풀이

나의 풀이 - 그리디

# 1:00 ~
def solution(book_time):
    book_minute = [] # book_time 을 '분'으로 변경
    for start, end in book_time:
        start_hh, start_mm = map(int, start.split(':'))
        end_hh, end_mm = map(int, end.split(':'))
        book_minute.append((start_hh * 60 + start_mm, end_hh * 60 + end_mm))
        
    # 퇴실 빠른 순 정렬    
    book_minute.sort(key=lambda x:x[1])
    
    cnt = 0
    visited = [0] * len(book_time)
    for idx, val in enumerate(book_minute):
        if visited[idx]:
            continue
        cnt += 1 # room 배정
        visited[idx] = 1
        out_idx = idx # 퇴실시간 인덱스
        for i in range(idx + 1, len(book_minute)):
            if visited[i]:
                continue
            if book_minute[i][0] >= book_minute[out_idx][1] + 10: # 퇴실시간 + 10분
                visited[i] = 1 # 같은 room 다른 시간대 배정
                out_idx = i # 퇴실시간 인덱스 갱신
        
    return cnt

• 테스트 케이스: 통과
• 제출 결과: 실패
  

다른 풀이 - 그리디

참고

def solution(book_time):

    # 시간을 분으로 변경하기
    def change_min(str_time):
        hh, mm = map(int, str_time.split(':'))
        return hh * 60 + mm
	
    # 대실 시작 시간이 빠른 순으로 정렬하기
    book_times = sorted([(change_min(x[0]), change_min(x[1]) + 10) for x in book_time])
    
    # 방 배정하기
    rooms = []
    for book_time in book_times:
        if not rooms: # 배정한 방이 하나도 없으면
            rooms.append(book_time)
            continue
        for index, room in enumerate(rooms): # 배정한 방이 있으면
            if book_time[0] >= room[-1]: # room[-1]은 퇴실 시간 (이미 +10 되어있음)
                rooms[index] = room + book_time # 그 방에 다른 시간대 대실 # 튜플끼리 더하기는 두 개의 튜플 합치기
                break
        else:
            rooms.append(book_time)
    return len(rooms)

• 테스트 케이스: 통과
• 제출 결과: 통과
  
• 문제에 주어진 book_time의 길이가 1000 이하이기 때문에 O(n^2)으로 풀어도 된다는 것을 감안하고 접근해야 한다고 한다.
• 나는 book_time 정렬할 때 대실 종료 시간이 빠른 순으로 정렬했는데, 이 풀이는 시작 시간이 빠른 순으로 정렬한다.

다른 풀이 - 힙

참고

from heapq import heappop, heappush

def solution(book_time):
    # "HH:MM" → HH * 60 + MM
    book_time_ref = [(int(s[:2]) * 60 + int(s[3:]), int(e[:2]) * 60 + int(e[3:])) for s, e in book_time]
    book_time_ref.sort() # 입실시간을 기준으로 오름차순 정렬
    
    heap = [] # 힙의 동작을 모방할 리스트
    cnt = 1 # 방의 개수
    for s, e in book_time_ref:
        if not heap:
            heappush(heap, e) # heap에 퇴실시간 푸시 # heappush는 기본적으로 최소힙으로 동작
            continue
        if heap[0] <= s: # 가장 빠른 퇴실시간이 입실 시간보다 빠르면 힙에서 제거한다.
            heappop(heap)
        else:
            cnt += 1
        heappush(heap, e + 10) # 청소시간 10분 # 가장 빠른 퇴실 시간을 기준으로 방을 비워야하므로 힙에 퇴실시간을 담는다.
    
    return cnt

• 테스트 케이스: 통과
• 제출 결과: 통과
  

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기