paiza スタック・キュー応用編 python 解答例

今回はこちらの解答例のない問題集を解いてみます。これから学習するかたへ参考になることが出来れば幸いです

まず

スタックキューにはいろいろライブラリがあるそうですが、以下の奴が一番早いそうです
左右どちらからの挿入と削除も出来ますので、大丈夫です

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つのスタック

スタックキューを３つ用意して追加と削除を繰り返しましょう
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

まず現在位置のマス目１をリストに入れておきましょう。このリストでどう移動してきたかを記録します
そしてtoリストを２次元リストとしておいて解いていきます

次に入力例２を見てみます
to[0][0]の要素２　があります。これは「一回目の移動を行う際、現在マス目１にいるのならばマス目２に移動する」ということです。インデックスにするためi回目のiとマス目xからそれぞれ1引いて[ i-1 ][ x-1 ]でリストの[ 0 ][ 0 ]を参照することになります

次に見るべき要素はto[1][1]の-1 です。「マス目２から２回目の移動を行う際の移動先」 です　-1ですのでマス目１に戻りました

次はto[0][2]の要素4です　いま自分はマス目１にいますのでtoリストのインデックス０(1-0で0)を見ます。そして３回目の移動ですので、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(読もうとしているページ数,その本のページ数)　とすることで、その本においてどれだけのページを読めるかを調べます。
読もうとするページ数が０になるまで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文でやってもよいですが、かなり面倒になりそうです。
そこで、グーを数値の０、チョキを１、パーを２とします。そして　
（自分の手-相手の手）％３の数値で判定します　（自分の手-相手の手）が-1　または2になった場合、３で割った余りは２です
余りが２になれば勝ち　１になれば負け　０であいこと判定します

あいこ　０　　余りは０
勝ち　-1 or 2　余りは２
負け　-2 or 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) #グーは０、チョキは１、パーは２
	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") #０なら引き分けです

満員エスカレーター

そのまま実装していきましょう

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))

カードゲーム

遊戯王かな？
めちゃくちゃ面倒です。
デッキ用の４０個の要素のリスト、墓地リスト、除外リストを用意し、デッキの[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")