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

문제

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

프로그래머스

풀이

나의 풀이(정확도 Max / 효율성 Low)

def solution(k, room_number):
    answer = []
    booked = dict()
    for num in room_number:
        room = num
        if booked.get(num,0): # 원하는 방이 있는 경우
            room = booked[num]
            while booked.get(room,0):
                room=booked[room]+1
        booked[num] = room
        booked[room] = room
        answer.append(room)
            
    return answer

정확도 테케는 다 맞았는데, 효율성에서 한개 테케만 통과

풀이

시간을 더 줄일 수 있는 방법을 찾아보고 고민해보다가, 경로 압축을 적용

(런타임 에러가 발생해서, 재귀 limit 늘려줌)

def find(booked,num):
    if booked.get(num,0):
        booked[num] = find(booked,booked[num]+1)
    else:    
        booked[num] = num

    return booked[num]

def solution(k, room_number):
    import sys
    sys.setrecursionlimit(1000000)
    answer = []
    booked = dict()
    for num in room_number:
        room = find(booked,num)
        answer.append(room)

    return answer