[프로그래머스] 호텔 방 배정, Python3

문제는 여기!

처음에는 재귀를 이용해서 문제를 풀었다. 풀이후 다른 사람들의 풀이 중에서 좀 더 깔끔하고 iterative하게 작성한 방식도 있었다. 여러 풀이를 보는 것과 깔끔한 코드를 짜는것도 중요하다고 느꼈던 문제! 풀이는 재귀를 이용한 풀이로 작성할 것이다.

제한사항 및 주의사항

신청 순서대로 방 배정을 하되, 배정된 방을 원한다면 원하는 방보다 크지만 배정받지 않은 방 번호중 제일 작은 번호를 배정한다.

k = 방 전체 갯수, 10 ** 12 이하

room_number 배열은 1 <= len(room_number) <= 200,000

풀이전략

k의 최댓값과 room_number의 크기가 200,000임을 고려해서 선형 방식으로 풀었다간 효율성 테스트에서 통과를 못한다.

해당 방을 배정받은 다음에는 배정받은 방 번호 + 1을 저장하는 딕셔너리를 선언하자.

ex) {1(방 번호) : 2(다음 방 번호)}

만약 이미 배정받은 방 번호를 원할 때는 재귀와 저장했던 딕셔너리를 이용해서 배정받지 않은 방 번호를 탐색해서 리턴해주는 방식을 이용하자. 그림을 통해 자세하게 살펴보자.

그림의 상황은 우선 두번째 고객까지 원하는 방이 비어있으므로, 호텔 방을 배정받은 상황이다.

세번째 고객은 1번 방을 배정받길 원하지만 1번방은 이미 배정이 된 상태다. 2번 방도 배정이 되어있고, 3번 방을 배정받아야 한다. 이 과정을 재귀로 풀었는데 그림으로 그 과정을 설명한다.

배정 받은 방이 있을경우 앞에서 호출한 방 번호를 리턴값으로 딕셔너리에 대입한 이유는 이후 다음 방 번호를 찾기 용이하기 때문에 시간 단축을 할 수 있다. 코드를 보면 좀 더 이해가 쉬울 것이다.

import sys
sys.setrecursionlimit(10000000)

def findEmptyRoom(number, rooms):
    if number not in rooms:
        rooms[number] = number + 1
        return number

    # 만약 배정 받은 번호라면 배정받지 않은 번호를 찾고 리턴 받은 다음, 리턴 값을
    # 딕셔너리에 넣어 다음 방 번호를 찾기 쉽게 하는 로직
    p = findEmptyRoom(rooms[number], rooms)
    rooms[number] = p + 1
    return p


def solution(k, room_number):
    answer = []
    rooms = dict()

    for number in room_number:
        emptyRoom = findEmptyRoom(number, rooms)
        answer.append(emptyRoom)

    return answer