プログラマー-ホテルの部屋を手配する

5791 ワード


質問する


プログラマー-ホテルの部屋を手配する 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