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

https://programmers.co.kr/learn/courses/30/lessons/64063

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

 

dic 과 재귀함수를 이용하여 빠르게 빈방을 찾아주도록 한다. 처음에는 아래의 방식과 비슷하게 구현하여 while 을 이용하여 dic[dic[]] 으로 구현했는데 시간 초과가 났다. 다른 블로그를 참고하니 재귀함수가 사용되었는데 앞으로 비슷한 문제가 나오면 이렇게 풀어야겠다. 

 

import sys

sys.setrecursionlimit(10000000)

def room_empty(i, dic):
    answer = 0
    
    if i not in dic:        
        dic[i] = i + 1
        answer = i    
    else:
        j = room_empty(dic[i], dic)
        dic[i] = j + 1
        answer = j
    
    return answer

def solution(k, room_number):
    answer = []
    dic = {}

    for i in room_number:
        answer.append(room_empty(i, dic))
    
    return answer

print(solution(10, [1, 3, 4, 1, 3, 1])) # [1, 3, 4, 2, 5, 6]