TIL#22 ALGORITHM(プリンタ)
問題の説明
一般的なプリンタでは、必要な印刷順に印刷されます.したがって、重要なドキュメントは後で印刷される可能性があります.この問題を解決するために,重要文書を先に印刷するプリンタを開発した.この新しく開発されたプリンタは、次のように印刷されます.
印刷待ちリストから、先頭の文書(J)を取り出す. 残りの個の印刷対象リストにJよりも重要なドキュメントがある場合は、Jを印刷対象リストの最後に配置します. でなければJを印刷します.
例えば、4つの文書(A、B、C、D)が印刷対象リストに順次存在し、重要度が2 1 3 2の場合、CD A Bの順に印刷される. 私が印刷を要求したドキュメントが何回目の印刷なのか知りたいです.上記の例では、Cは1位、Aは3位である.
ソリューション関数を作成してください.パラメータが現在のキュー・リスト内のドキュメントの重要度のソート順と、印刷を要求したドキュメントが現在のキュー・リスト内にある場所を指定した場合、印刷を要求したドキュメントの何回目の印刷かを返します.
せいげんじょうけん
現在のキュー・リストには、100個未満の1つ以上のドキュメントが含まれています.
印刷ジョブの重要性は1~9で表され、数字が大きいほど重要です.
locationには0未満の値(現在のキューリストのタスク数-1)があり、キューリストの一番前にある場合は0、2番目にある場合は1と表示されます.
I/O例
例1
問題の例は次のとおりです.
例2
6つの文書(A、B、C、D、E、F)は、印刷対象リストにおいて、重要度が1 1 1 1 9 1 1 1 1であり、C D E F A Bの順に印刷される.
列挙方法を使用して優先度パラメータのリストをリストし、(0,1)0個のインデックス配列の要素の2番目のインデックス配列の優先度の要素インデックス値をtupleの形式で配列に挿入し、新しいarr配列 を生成する
while arrがある場合は繰り返し、一番前の要素から取り出し、配列の最大値と比較し、それ以上であればcountに1を加算します.
max(arr)より小さい場合は、配列の末尾に再配置します.
実行中にエラーが発生するためです.
したがって,抽出,抽出,挿入を継続する方式はあまり有効ではないと考えられ,dequeを用いてキュー資料構造の形式でコードを再記述した.
優先配列をdequeに入れcount変数を0 に初期化する. while deqがなくなるまで、繰り返し文を使用して を繰り返します. deq[0]インデックスの[0]次値が最大値(deq)[0]より小さい場合、
Dequeのrotate-1を利用すると、左に押した0番目のインデックスが最後になります.
(rotate使用、pop再追加不要) deq[0]インデックスの[0]次値が最大(deq)[0]次値以上である場合、count+1が計算され、deqから減算される. から減算された値のインデックスが位置と同じである場合、重複は停止され、countに戻ります.
一般的なプリンタでは、必要な印刷順に印刷されます.したがって、重要なドキュメントは後で印刷される可能性があります.この問題を解決するために,重要文書を先に印刷するプリンタを開発した.この新しく開発されたプリンタは、次のように印刷されます.
印刷待ちリスト
例えば、4つの文書(A、B、C、D)が印刷対象リストに順次存在し、重要度が2 1 3 2の場合、CD A Bの順に印刷される.
ソリューション関数を作成してください.パラメータが現在のキュー・リスト内のドキュメントの重要度のソート順と、印刷を要求したドキュメントが現在のキュー・リスト内にある場所を指定した場合、印刷を要求したドキュメントの何回目の印刷かを返します.
せいげんじょうけん
現在のキュー・リストには、100個未満の1つ以上のドキュメントが含まれています.
印刷ジョブの重要性は1~9で表され、数字が大きいほど重要です.
locationには0未満の値(現在のキューリストのタスク数-1)があり、キューリストの一番前にある場合は0、2番目にある場合は1と表示されます.
I/O例
priorities location return
[2, 1, 3, 2] 2 1
[1, 1, 9, 1, 1, 1] 0 5
I/O例説明例1
問題の例は次のとおりです.
例2
6つの文書(A、B、C、D、E、F)は、印刷対象リストにおいて、重要度が1 1 1 1 9 1 1 1 1であり、C D E F A Bの順に印刷される.
インプリメンテーションロジック
列挙方法を使用して
def solution(priorities, location):
arr = [(i[1],i[0]) for i in enumerate(priorities)] >> [(1,0),(1,1),(9,2),(1,3),(1,4),(1,5)]
solution([1,1,9,1,1,1], 5):
while arrがある場合は繰り返し、一番前の要素から取り出し、配列の最大値と比較し、それ以上であればcountに1を加算します.
max(arr)より小さい場合は、配列の末尾に再配置します.
イニシャルコード
def solution(priorities, location):
arr = [(i[1],i[0]) for i in enumerate(priorities)]
count = 0
while arr:
select_doc = arr.pop(0)
if len(arr) == 0:
break
if select_doc[0] >= max(arr)[0]:
count += 1
if select_doc[1] == location:
return count
else:
arr.append(select_doc)
テストケース2、5、18号が通らなかったので考えてみましたが、配列の長さが1なら問題です.実行中にエラーが発生するためです.
したがって,抽出,抽出,挿入を継続する方式はあまり有効ではないと考えられ,dequeを用いてキュー資料構造の形式でコードを再記述した.
Dequeで書き換えたコード
from collections import deque
def solution(priorities, location):
deq = deque((i[1],i[0]) for i in enumerate(priorities))
count = 0
while deq:
if deq[0][0] < max(deq)[0]:
deq.rotate(-1)
elif deq[0][0] >= max(deq)[0]:
count += 1
a = deq.popleft()
if a[1] == location:
return count
コードの説明
[(1,0),(1,1),(9,2),(1,3),(1,4),(1,5)] 튜플의 0번인덱스는 priorities배열의 요소, 1번인덱스는 priorities배열의 요소 인덱스를
while deq:
Dequeのrotate-1を利用すると、左に押した0番目のインデックスが最後になります.
if deq[0][0] < max(deq)[0]:
deq.rotate(-1)
elif deq[0][0] >= max(deq)[0]:
count += 1
a = deq.popleft()
if a[1] == location:
return count
Reference
この問題について(TIL#22 ALGORITHM(プリンタ)), 我々は、より多くの情報をここで見つけました https://velog.io/@tgrf07/TIL22-ALGORITHM-프린터テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol