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

문제설명

출처 : 프로그래머스 코딩테스트 연습 문제 - 호텔 대실

해결코드

그리디를 사용해서 구현하였다. 문제에 주어진 book_time의 길이 즉 예약이 1000개 이하기 때문에 O(n2)으로 풀어도 된다는 것을 감안하고 접근하였다.

def solution(book_time):

    # 풀이설명1 : 함수 만들기
    def change_min(str_time: str) -> int:
        return int(str_time[0:2]) * 60 + int(str_time[3:])
	
    #풀이 설명2 : 예약 시간이 빠른 순으로 정렬하기
    book_times = sorted([[change_min(i[0]), change_min(i[1]) + 10] for i in book_time])
	
    #풀이 설명3 : 방 배정하기
    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]:
                rooms[index] = room + book_time
                break
        else:
            rooms.append(book_time)
    return len(rooms)

코드해설

코드 해설은 입출력 예제 1번을 통해 진행하도록 하겠습니다.

 

풀이설명1

# 풀이설명1 : 함수 만들기
def solution(book_time):
    def change_min(str_time: str) -> int:
        return int(str_time[0:2]) * 60 + int(str_time[3:])

먼저 입력받는 타입이 리스트이며, str로 구성되어 있기 때문에 숫자로 전환을 해줄 필요가 있습니다.

 

풀이설명2

#풀이 설명2 : 예약 시간이 빠른 순으로 정렬하기
book_times = sorted([[change_min(i[0]), change_min(i[1]) + 10] for i in book_time])

방에 들어갈 수 있는 한 최대한 고객을 배정해야 되기 때문에 (ex. 빈방이 놀고 있으면 안됨.) 예약 시간이 빠른 순으로 넣어보면서 방이 차 있으면 다른 방을 배정하면 된다.

 

풀이설명3

#풀이 설명3 : 방 배정하기
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]:
            rooms[index] = room + book_time
            break
    else:
        rooms.append(book_time)
return len(rooms)

핵심이 되는 메인로직입니다. 저는 처음에 방을 배정하기 위해 해쉬 테이블을 활용해 문제를 접근하려 했으나 곰곰히 생각해 보니 rooms 라는 [ ] 를 만들고 잘 정렬해서 예약받은 book_times의 시간대별로 고객들을 넣어주면 되지 않을까? 로 접근했습니다. 

 

위 코드의 동작 원리는 다음과 같습니다. 입출력 예제 1번 기준으로 설명하겠습니다.

정렬된 book_times는 다음과 같습니다. [[850, 1170], [860, 930], [900, 1030], [1000, 1110], [1100, 1290]]

1.  [850, 1170] 시간대가 먼저 rooms가 생성되면서 비어있기 때문에 rooms에 추가 됩니다.
2.  rooms에 [850, 1170]이 들어가겠죠. 즉 rooms의 0번 인덱스 [850, 1170] 예약이 추가 된 겁니다.
3.  여기가 제가 구현한 코드의 핵심입니다. 인덱스 번호를 호텔의 호실이라고 생각해보죠.
4. 0번 호실에는 [850, 1170] 시간대가 예약이 되어 있습니다. 때문에 다음 예약 [860, 930]은 새로운 방에 배정받아야 됩니다.
5. 때문에 [860, 930]은 그대로 rooms에 append가 되면서 1호실을 가지게 되겠죠.
6. 그 다음 [900, 1030] 예약이 들어온다면 어떻게 해야 될까요? 제가 만든 rooms를 다 순회해 보는 겁니다. 0호실 예약 가능? 1호실 예약 가능? 하지만 예약이 가능하지가 않죠. 때문에 이 또한 그대로 rooms에 append가 되면서 2호실을 가지게 되겠죠.
7. 다음으로 [1000, 1110]이 예약은 어디로 가야될까요? 비어있는 방이 있는지 for문으로 계속 돌릴겁니다. 
8. 1호실 방이 비어 있군요. 어떻게 아냐고요?  1호실 방(rooms[1])은 930이 나가고 청소를 마친 시간이기 때문에 지금 예약하려는 시간보다 작거나 같거든요.
9. 그렇다면 새로운 예약마다 호실을 탐색하면서 호실의 마지막 인덱스(마지막으로 손님이 나가고 청소한 시간) 새로 예약하는 시간보다 작거나 같다면, 손님이 들어올 수 있습니다.
10. 그렇다면 1호실은 [860, 930] 밖에 없던 예약을 [860, 930, 1000, 1110]으로 늘려줘야 됩니다.
11. 이는 코드상으로 rooms[index] = room + book_time 으로 구현했습니다.
12. 이와 같은 로직을 반복하면 각 호실(사실 rooms의 인덱스)를 순회해 보면서 최대한 예약을 우겨 넣을 수 있겠죠.
13. 이를 반복하면 가장 최선의 결과 즉 최소의 방을 배정하는 해결책이 됩니다.