[2019 카카오 인턴십] 호텔 방 배정 (feat. PYTHON)

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

    for i in room_number:
        reserve = i
        while True:
            if reserve in rooms:
                reserve += 1
            else:
                rooms[reserve] = 1
                ret.append(reserve)
                break

    return ret

 

풀이

1. 방번호 리스트를 생성한 후 원하는 방이 있으면 방을 주고 리스트에서 지워준다.

2. 방이 없을시 남은 방중에서 원하는 방보다 큰번호의 방을 주고 마찬가지로 리스트에서 지워준다.

위의 풀이법은 정확성은 100%지만 효율성은 다 실패했다.

다른사람이 푼걸 보고,  다시 풀어보자.

다른사람의 풀이

재귀로 푸는 방법과 재귀를 루프로 풀어 푸는 방법이 있다.

 

import sys
sys.setrecursionlimit(10000000) # 설정해주지 않으면 재귀가 많이 일어나면서 런타임에러 등이 나타날 수 있다.

def findEmptyRoom(number, rooms): # 빈방을 찾는 함수
    if number not in rooms:        
        rooms[number] = number + 1
        return number
    
    empty = findEmptyRoom(rooms[number], rooms)
    rooms[number] = empty + 1
    return empty


def solution(k, room_number):
    answer = []
    rooms = dict() # 몇번 방이 비어있는지 체크하는 딕셔너리

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

 

def solution(k, room_number):
    room_dic = {}
    ret = []
    for i in room_number:
        n = i
        visit = [n]
        while n in room_dic:
            n = room_dic[n]
            visit.append(n)
        ret.append(n)
        for j in visit:
            room_dic[j] = n+1
    return ret

 

문제해설 https://tech.kakao.com/2020/04/01/2019-internship-test/

[문제4 풀러 가기]