[프로그래머스 Lv.4] 호텔 방 배정 (Python)

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

프로그래머스

풀이

레벨 4의 난이도를 자랑하는 문제답게 정말 아이디어를 떠올리기가 어려운 문제였다.

우선 필자는 처음에 배열에다가 배정 여부를 저장하고 이를 사용하여 문제를 해결하고자 하였다. 하지만 이렇게 하면 k의 크기가 최대 "1조"이기 때문에 시간 초과는 물론이고, 어마무시한 배열의 크기 때문에 메모리 부족으로 인한 런타임 에러가 발생한다. (int를 담는 배열이라고 가정하면 int형이 4바이트이므로 4조 바이트, 약 4 테라바이트)

그렇기 때문에 애초에 배열로 문제를 풀 생각을 하면 안 되는 것이었다. (하지만 필자는 이를 고려하지 않고 문제를 풀었으나 실제 채점 시에 런타임 에러가 발생...)

 

배열을 쓸 수 없을 시에 생각해볼 수 있는 방법은 역시 딕셔너리를 사용하는 방법이다. 딕셔너리를 사용하면 k개의 공간을 미리 잡고 있을 필요도 없고, O(1) 시간에 원하는 자료에 접근할 수 있기 때문에 시간 복잡도 측면에서도 훨씬 자유로워지기 때문이다.

위와 같이 생각하여 딕셔너리를 사용하여 현재 방의 정보를 체크하고, 비었다면 즉시 반환하고 이미 배정되었다면 재귀적으로 다음 방을 찾아가도록 하였다. 하지만 역시나 딕셔너리를 사용한 방법으로도 다음과 같은 최악의 상황을 해결할 수가 없다.

만약 한 방에만 모든 사람들이 배정 요청을 하는 상황을 가정해 보자. 문제에서 최대 인원이 20만 번이라고 했으므로 만약 모든 사람이 한 방에만 요청을 한다면 처음에 즉시 처리된 사람을 제외하고는 2번째 사람은 재귀를 1번, 3번째 사람은 2번,... , 20만 번째 사람은 재귀를 19만 9999번 반복해야 한다. 그렇게 되면 총 처리되는 함수의 수는 등차수열의 합 공식에 의해 200000 * (1 + 199999) / 2 = 20000000000, 무려 2백억 번 함수를 실행해야 하는 것이다. 그렇기에 딕셔너리를 사용하여 조회의 시간복잡도가 아무리 O(1)이라고 해도 시간 초과가 발생할 수밖에 없다.

 

위에서의 상황을 살펴보면 요청한 방이 이미 차있을 때 비어있는 다음 방을 찾는 과정에서 문제가 발생했다는 것을 알 수 있다. 그래서 이 과정을 더 효율적으로 해결할 수 있는 방법을 찾아야한다.

그 방법은 바로 딕셔너리의 key를 해당 방의 방문 여부로 생각하고, 딕셔너리의 value를 해당 방 이후의 빈 방으로 저장하는 것이다.

해당 방 이후의 빈 방을 딕셔너리의 value로 설정함으로써 앞서 사용했던 방법에서의 문제였던 비어있는 다음 방을 찾는 과정을 재귀 없이 O(n)의 조회 과정을 통해 즉각적으로 알 수 있기 때문에 시간 복잡도 측면에서 극명한 개선 효과를 얻을 수 있다.

 

하지만 이렇게까지 해도 런타임 에러가 발생하는데 파이썬의 재귀는 기본적으로 1000번 정도가 한계인데 이를 넘어선 수의 재귀가 발생하기 때문이다. 최종적으로 재귀 함수 호출 제한을 int의 최댓값인 2^31 - 1으로 설정하니 정확도와 효율성 테스트 모두 통과할 수 있었다.

 

무려 배열 -> 딕셔너리 -> 딕셔너리 사용 방식의 변경 -> 재귀 호출 상한 변경, 이렇게 4번의 고민을 통해 문제를 해결할 수 있었다. 확실히 레벨 4의 벽은 높다는 사실을 깨달았다.

import sys
sys.setrecursionlimit(2**31 - 1) # int의 최대값인 2**31 - 1만큼 재귀할 수 있도록 설정, int 범위를 벗어나면 OverflowError 발생

def solution(k, room_number):
    rooms = {} # key: 이미 방문한 방, value: 다음 방 중 비어있는 방
    for number in room_number: # 각 사람이 희망하는 번호로부터 시작하여
        find_empty_room(rooms, number) # 빈 방을 딕셔너리에 기록
    return list(rooms) # 딕셔너리의 키에 방문한 방들을 담아놓았으므로 list로 키들만 출력

def find_empty_room(rooms, number): # 빈 방을 반환하는 재귀함수
    if number not in rooms: # 방이 비었을 때
        rooms[number] = number + 1 # 다음 방이 비었음을 기록
        return number # 빈 방의 번호 반환
    empty = find_empty_room(rooms, rooms[number]) # 방이 차있다면 빈 방을 찾을 때까지 비었다고 기록되어진 방을 재귀적으로 탐색
    rooms[number] = empty + 1 # 찾은 빈 방을 배정하고 다음 방이 비었음을 기록
    return empty # 빈 방의 번호 반환