문제

프로그래머스 - 호텔 방 배정
k개 방이 있는 호텔에 투숙하려는 고객들에게 방을 배정하려고 한다.
각 방은 1 ~ k번까지 번호로 구분되어있고, 처음에는 모든 방이 비어있다.
다음 규칙에 따라 고객에게 방을 배정한다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정한다.
2. 고객은 투숙하기 원하는 방 번호를 제출한다.
3. 고객이 원하는 방이 비어있다면 즉시 배정한다.
4. 고객이 원하는 방이 이미 배정되어 있으면, 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정한다.

아이디어

핵심 아이디어

• 호텔의 각 방을 Node로 만든다. 방의 최대 갯수는 10^12개 이므로 미리 만들지 않고 실제 사용할때 만든다.
• 각 Node들이 가리키는 다른 Node는 현재 방이 차 있을 경우, 배정될 다른 방을 의미한다.
  1. 초기 상태에는 Node들은 자기 자신을 가리키고 있다.
  2. 고객이 n Node방에 배정이 된다면 n+1 Node방이 가리키고 있는 Node를 가리킨다..
  3. 누군가 n Node방을 다시 요청할 경우, n Node이 가리키는 방을 찾아 배정한 후 2번과정을 다시 반복한다.

그림으로 표현하면 다음과 같다.

• 이 때, 화살표는 1번 방(노드)의 다음 방은 2번 방(노드)이라는 것을 의미한다.
  
  
• 3번 노드가 4번 노드를 가리키고 있을 때, 4번 노드가 5번 노드를 가리킬 경우 한가지 수정작업을 거치는 것이 좋다.
• 3번 노드가 4번 노드를 계속해서 가리키고 있어도 계산에는 상관없지만 5,6,7,8,... 노드가 계속 연결될 경우 누군가 3번노드를 다시 요청하게 될 때, 4,5,6,7... 등 연결되어있는 모든 노드를 다시 탐색하게 된다.
• 따라서 3번 노드가 가리키는 방 또한 새로운 4번 노드와 동일하게 한다.
  
• 2번 방을 사용할 때를 예시로 좀 더 자세하게 그림을 그려보았다.
• 2번 방을 사용할 경우, 3번방을 가리키게 된다.
  이때, 3번방은 이미 5번방을 가리키고 있으므로 2번방이 3번방을 가리키는 상태로 둔다면 후에 비효율 적인 검색을 하게 될 수 있다.
  그러므로 2번방 또한 3번방과 마찬가지로 5번방을 가리키도록 하게 한다.
  동시에 1번방 또한 2번방을 가리키고 있지만 2번방은 5번방을 가리키고 있으므로 1번방도 5번방을 가리키게 한다.

구현 아이디어

1. 각 노드와 가리키는 방은 dict자료구조를 이용한다.
   key값은 방 번호, value값은 가리키는 방 번호를 의미하도록 한다.
2. 재귀를 이용하여 각 방들이 가리키는 방을 갱신한다.
   • (종료 조건) 현재 방이 가리키는 값이 기본값이라면 answer에 현재 방을 추가하고, 현재 방 번호를 반환한다.
   • 현재 방이 가리키는 방 번호를 매개변수로 하여 재귀함수를 실행한다.
   • 반환 된 값을 현재 방이 가리키는 방 번호로 한다.

코드

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)  # 재귀가 너무 깊게 시행될 경우 효율성 체크에서 런타임 에러가 뜰 수있다.

def solution(k, room_number):
    answer = []
    info = defaultdict(int)  # 새로운 key를 사용할 때, 기본값 int를 사용하는 값을 만들어준다.
    
    def find_nxtroom(num: int) -> int:
        if info[num] == 0:  # 기본값일 경우 재귀를 종료한다.
            answer.append(num)
            info[num] = num + 1
            # 다음 방을 지정해준다. 
            # 이때에는 num + 1번방이 다른 방을 가리키고 있는지는 알지 못하지만 
            # 다음에 현재 방보다 작은 번호를 요청할 경우 값이 갱신될 것이다.
            return num + 1  
        
        info[num] = find_nxtroom(info[num])
        return info[num]
    
    for i, r in enumerate(room_number):
        find_nxtroom(r)
        
    return answer