今回はこちらの解答例のない問題集を解いてみます。これから学習するかたへ参考になることが出来れば幸いです
まず
スタックキューにはいろいろライブラリがあるそうですが、以下の奴が一番早いそうです
左右どちらからの挿入と削除も出来ますので、大丈夫です
from collections import deque
s = deque([])
s.append(1) # 右に挿入
s.appendleft(2) # 左に挿入
s.pop() # 右の要素を削除
s.popleft() # 左の要素を削除
またキューの挿入、削除のクエリを受け取る場合、何個の文字が来るか分からないことがあります。そこで
str,*x = input().split()
とすることで、xに相当する文字が存在した場合、xにリストとして格納することが出来ます
もし、xにあてがう文字が無かったとしてもエラーになりません
つまり変数と受け取る要素の数を合わせる必要がなくなります
例
str,*x = "add",1,2,3,4
# strはadd
# xは[1, 2, 3, 4]になる この1,2,3,4が仮になかったとしてもエラーにならない
#数字で受け取ることがほとんどですのでint(x[0])などと変更してください
他にもこんな感じの使い方も出来ます
とりだす時は、y[0],y[2]のようにリストを使う時と同じです
x,*y,z = 1,2,3,4,5,6
# xは1
# yは[2, 3, 4, 5]
# zは6
解答例
3つのスタック
スタックキューを3つ用意して追加と削除を繰り返しましょう
while q1: というのは、「リストに要素がある限り」 という条件式です
from collections import deque
q1 = deque([])
q2 = deque([])
q3 = deque([])
N = int(input())
for i in range(N):
str,*x = input().split()
if str=="push":
if x[0]=="1":q1.append(x[1])
elif x[0]=="2":q2.append(x[1])
else: q3.append(x[1])
else:
if x[0]=="1":q1.pop()
elif x[0]=="2":q2.pop()
else:q3.pop()
while q1:
print(q1.pop())
while q2:
print(q2.pop())
while q3:
print(q3.pop())
レンタルビデオ店
左右どちらから挿入、削除するかこんがらがりそうになります
from collections import deque
q = deque([])
N = int(input())
for i in range(N):
q.appendleft(input())
K = int(input())
for i in range(K):
str,*x = input().split()
if str=="return":
q.appendleft(x[0])
else:
q.popleft()
while q:
print(q.popleft())
warp
まず現在位置のマス目1をリストに入れておきましょう。このリストでどう移動してきたかを記録します
そしてtoリストを2次元リストとしておいて解いていきます
次に入力例2を見てみます
to[0][0]の要素2 があります。これは「一回目の移動を行う際、現在マス目1にいるのならばマス目2に移動する」ということです。インデックスにするためi回目のiとマス目xからそれぞれ1引いて[ i-1 ][ x-1 ]でリストの[ 0 ][ 0 ]を参照することになります
次に見るべき要素はto[1][1]の-1 です。「マス目2から2回目の移動を行う際の移動先」 です -1ですのでマス目1に戻りました
次はto[0][2]の要素4です いま自分はマス目1にいますのでtoリストのインデックス0(1-0で0)を見ます。そして3回目の移動ですので、to[ 0 ]リストの(3-1)で2の要素を取得します
このように行のインデックスにはマス目を、列のインデックスには何回目かを入れていきます
また
-1以外の要素が出てきた場合にはスタックに移動先を積み上げるようにして記憶させておきます
-1がでてきたときは積み上げてきたスタックの一番上の要素が一個前のマス目になりますのでこれをリストに追加します
from collections import deque
q = [1]
s = deque([])
N,K = map(int,input().split())
to = [[int(i)for i in input().split()]for _ in range(N)]
for i in range(K): # 変数iは何回目かを表す数値 列のインデックスにいれます
if to[q[-1]-1][i]==-1: # 行は移動してきたマス
# を表すリストの最後の要素(現在位置)です
q.append(s.pop())
else:
s.append(q[-1]) #-1でないなら現在位置を記憶させてから、移動先をqに追加
q.append(to[q[-1]-1][i])
for i in q[1:]:
print(i)
積読
読むときどういう操作をするかが重要です
まず一番上の本のページ数を取り出します。次に読むページ数と本のページ数を比較して最大何ページ読めるかを求めます
min(読もうとしているページ数,その本のページ数) とすることで、その本においてどれだけのページを読めるかを調べます。
読もうとするページ数が0になるまでwhile文で処理します
from collections import deque
q = deque([])
N = int(input())
for i in range(N):
str,x = input().split()
x = int(x)
if str=="buy_book":
q.append(x)
else:
while x>0: # xは読もうとしているページ数
page = q.pop() #一番上の本のページ数
read = min(x,page) # その本において何ページ読めるか
x -= read #それぞれから引く
page -= read #
if page>0:#本のページが残っていれば読破していないので積み上げ直す
q.append(page)
print(len(q))
print(sum(q))
満員エレベーター
if文などでそのまま実装していきましょう
from collections import deque
q = deque([])
N,X = map(int,input().split())
for i in range(N):
str,*x = input().split()
if str=="ride":
for v in x[1:]:
if sum(q)+int(v)<=X:
q.append(int(v))
else:
for k in range(int(x[0])):
q.pop()
print(len(q))
print(sum(q))
3つのキュー
スタックのところとほぼ同じですねキューになっただけです キューなので筒のような感じです
from collections import deque
q1 = deque([])
q2 = deque([])
q3 = deque([])
N = int(input())
for i in range(N):
str,*x = input().split()
if str=="push":
if x[0]=="1":q1.append(x[1])
elif x[0]=="2":q2.append(x[1])
else: q3.append(x[1])
else:
if x[0]=="1":q1.popleft()
elif x[0]=="2":q2.popleft()
else: q3.popleft()
while q1:
print(q1.popleft())
while q2:
print(q2.popleft())
while q3:
print(q3.popleft())
品出し
そのまま実装しましょう
from collections import deque
q = deque([])
N = int(input())
for i in range(N):
str,x = input().split()
if str=="add":
q.append(x)
else:
for k in range(int(x)):
q.popleft()
while q:
print(q.popleft())
キューじゃんけん
じゃんけんの勝ち負けあいこ判定をそのままif文でやってもよいですが、かなり面倒になりそうです。
そこで、グーを数値の0、チョキを1、パーを2とします。そして
(自分の手-相手の手)%3の数値で判定します (自分の手-相手の手)が-1 または2になった場合、3で割った余りは2です
余りが2になれば勝ち 1になれば負け 0であいこと判定します
あいこ 0 余りは0
勝ち -1 or 2 余りは2
負け -2 or 1 余りは1
from collections import deque
N,K = map(int,input().split())
pa = deque([])
ky = deque([])
for i in range(N):
x,y = input().split()
if x=="R":pa.append(0) #グーは0、チョキは1、パーは2
elif x=="S":pa.append(1)
else: pa.append(2)
if y== "R":ky.append(0)
elif y== "S":ky.append(1)
else:ky.append(2)
ans = 0
for i in range(K):
p = pa.popleft() #paiza
k = ky.popleft() #kyoko
if (p-k)%3==2:
ans += 1 #paizaの勝ち
elif (p-k)%3==1:
ans -= 1 #paizaの負け
a,b = input().split()
if a=="push":pa.append(p)
if b=="push":ky.append(k)
if ans > 0:
print("paiza") #ansが正であればpaizaが勝ち越し負であれば負け越し
elif ans < 0:
print("kyoko")
else:
print("draw") #0なら引き分けです
満員エスカレーター
そのまま実装していきましょう
from collections import deque
q = deque([])
N,X = map(int,input().split())
for i in range(N):
str,*x= input().split()
if str=="ride":
for v in x[1:]:
if sum(q)+int(v)<=X:
q.append(int(v))
else:
if int(x[0])>len(q):
q.clear()
else:
for j in range(int(x[0])):
q.popleft()
print(len(q))
print(sum(q))
カードゲーム
遊戯王かな?
めちゃくちゃ面倒です。
デッキ用の40個の要素のリスト、墓地リスト、除外リストを用意し、デッキの[n-1]番目に適当に"Key"と入れます
左右どちらから挿入、削除するか気を付けながら実装してください。
カードを引く行為が来たら一個ずつ引いて、キーカードだったらそこでプログラム終了
見やすくするために関数を作って処理していますが、普通にif文でも文量変わらなそう
from collections import deque
N,K = map(int,input().split())
deck = deque([None] * 40)
deck[N - 1]= "key"
gra = deque([])
lost = deque([])
n = input()
for i in range(5):
a = deck.popleft()
if a=="key":
print(1)
exit()
def draw(i):
for k in range(i):
a = deck.popleft()
if a == "key":
return True
return False
def discard(i):
for k in range(i):
gra.appendleft(deck.popleft())
def re_gra(i):
for k in range(i):
deck.append(gra.popleft())
def exc(i):
for k in range(i):
lost.appendleft(deck.popleft())
def re_exc(i):
for k in range(i):
deck.append(lost.popleft())
for i in range(2,K+1):
str,x= input().split()
x = int(x)
if str=="draw":
if draw(x):
print(i)
exit()
elif str=="discard":discard(x)
elif str=="return_from_the_graveyard":re_gra(x)
elif str=="exclude":exc(x)
else:re_exc(x)
print("Lose")