호텔방 배정

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

프로그래머스

---

1차 시도

방 번호를 key를 갖고 바로 다음 방 번호를 value로 두고 찾아보자는 생각으로 구현

def solution(k, room_number):
    room_dict = dict()
        
    for room in room_number:
        while room in room_dict.keys():
            room = room_dict[room]
        room_dict[room] = room + 1
    
    return list(room_dict.keys())

결과: 78.8

정확성만 통과

 

다른 사람 코드

import sys
sys.setrecursionlimit(1012)

def solution(k, room_number):
    room_dict = dict()
        
    for room in room_number:
        find_empty_room(room, room_dict)
            
    return list(room_dict.keys())

def find_empty_room(room_num, room_dict):
    if room_num not in room_dict.keys():
        room_dict[room_num] = room_num + 1
        return room_num
    empty_room = find_empty_room(room_dict[room_num], room_dict)
    room_dict[room_num] = empty_room + 1
    return empty_room

결과: 100

정확성과 효율성 모두 통과

 

1차 시도와 차이점

저의 코드는 value를 바로 다음 방 번호를 넣기 때문에 다음 가능한 방 번호를 찾을 때 어떠한 경우라도 1씩 증가시키면서 찾습니다.

다른 사람 코드는 value를 이전까지 찾았던 배정 가능한 빈 방 번호를 넣기 때문에 1씩 증가시키는 것보다 탐색 경로가 압축이 되기 때문에 더 빠르게 됩니다.