質問する

プログラマー-ホテルの部屋を手配する k号室にチェックインしたお客様のために部屋を手配します.
各部屋番号は1 ~ k番で、最初はすべての部屋が空いていました.
以下の規則に従ってお客様に部屋を手配します.

部屋は申請のたびに手配されます.

お客様がチェックインしたい部屋番号を提出します.

お客様が希望する部屋が空いている場合は、すぐに手配します.

お客様が希望する部屋が手配されている場合は、希望する部屋よりも番号が大きく、空き部屋の中で番号が一番小さい部屋を手配します.

アイデア

コアクリエイティブ

ホテルの各部屋をNodeに変更します.部屋の最大数は10^12個なので、事前に作る必要はなく、実際の使用時に作ることができます.

各Nodeが指す他のNodeは、現在部屋があれば別の部屋を手配することを示しています.

の初期には、Nodeは自分を指していた.

クライアントがn Node号室に割り当てられた場合、n+1 Node号室がNode号室を指す.

もし誰かが再び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号室を指す.

実施形態

各ノードと指定された部屋はdictの資料構造を採用している.key値は部屋番号、value値は部屋番号を表します.

の復帰を利用して、各部屋が指す部屋を更新します.

(終了条件)現在の部屋がデフォルト値である場合、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