プログラマー-ホテルの部屋を手配する
5791 ワード
質問する
プログラマー-ホテルの部屋を手配する k
号室にチェックインしたお客様のために部屋を手配します.
各部屋番号は1 ~ k
番で、最初はすべての部屋が空いていました.
以下の規則に従ってお客様に部屋を手配します.
アイデア
コアクリエイティブ
Node
に変更します.部屋の最大数は10^12個なので、事前に作る必要はなく、実際の使用時に作ることができます.Node
が指す他のNode
は、現在部屋があれば別の部屋を手配することを示しています.Node
は自分を指していた.n Node
号室に割り当てられた場合、n+1 Node
号室がNode
号室を指す.n Node
部屋を申請したら、n Node
が指す部屋を見つけて、手配してから2番目の過程を繰り返します.この場合、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
Reference
この問題について(プログラマー-ホテルの部屋を手配する), 我々は、より多くの情報をここで見つけました
https://velog.io/@yanghs0540/프로그래머스-호텔-방-배정
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
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
Reference
この問題について(プログラマー-ホテルの部屋を手配する), 我々は、より多くの情報をここで見つけました https://velog.io/@yanghs0540/프로그래머스-호텔-방-배정テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol