호텔 방 배정

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

코딩테스트 연습 - 호텔 방 배정

2019 카카오 개발자 겨울 인턴십 문제 중 하나입니다. 1~k까지 번호가 붙은 k개의 방이 있고, 초기에는 모든 방이 비어있습니다. 고객들은 각자 원하는 방 번호를 제출하고 원하는 방이 비어있으면 해당 방에, 이미 차 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 작은 방에 투숙하게 됩니다. 전체 방 개수와 고객들이 원하는 방 번호가 순서대로 들어있는 배열이 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return하면 됩니다.

 

import sys
sys.setrecursionlimit(10000) #안 쓰면 효율성 검사에서 틀림

def find_empty_room(num, room_dic):
    if num not in room_dic:    #num 에 배정 가능
        room_dic[num] = num+1  #다음 num을 찾는 고객은 num+1번 방을 체크 
        return num
    else:
        new = find_empty_room(room_dic[num], room_dic)
        room_dic[num] = new+1
        return new
        

def solution(k, room_number):
    dic = {}
    ans = []
    for n in room_number:
        a = find_empty_room(n, dic)
        ans.append(a)
    return ans

딕셔너리와 재귀를 이용해서 풀었습니다. 딕셔너리의 key값 m이 존재하면 m번 방에는 이미 고객이 차 있다는 것이고, dic[m]는 m번 방을 찾는 고객을 dic[m]이 나타내는 방으로 보내서 dic[m]번 방에 고객이 있는지를 재귀로 확인하면 됩니다. 문제 조건에 원하는 방이 차 있는 고객은 무조건 그 방보다 번호가 큰 방에 투숙해야 하기 때문에 dic[num] = num+1로 두었습니다. 만약 num+1번 방에도 고객이 있다면? num+2번 방으로 재귀를 이용해 보내겠죠!

 

백준에서 문제를 풀다 보면 input() 대신 sys.stdin.readline()을 이용해야 시간 제한에 걸리지 않는 경우가 있습니다. 마찬가지로 재귀함수를 이용해서 문제를 풀게 될 경우 최대 깊이를 설정하지 않으면 이 문제처럼 틀리는 경우가 발생할 수 있습니다. 파이썬 코딩 도장(https://dojang.io/mod/page/view.php?id=2358)에 따르면 파이썬 인터프리터 소스 코드(C 언어)에는 최대 재귀 깊이가 1,000으로 정의되어 있다는데, 뒤에 0을 하나 더 붙여서 10000을 최대 재귀 깊이로 설정하니 문제가 풀리네요.