第133回【Python】アイドルグループ
現在取り組んでいるのは、paiza ラーニング問題集「クエリメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
Python をゼロから勉強してみよう、のコーナー 133 回目です。
忙しい時に限って掃除がしたくなります。突然会社の机をアルコールタオルで拭いて回っていたら、みんなが気を遣って席を空けてくれました。現実逃避で今やる必要がないことをしているのに、なんか迷惑をかけているみたいで申し訳ない気持ちになりました。
それでは、今日も頑張ってみようと思います。
アイドルグループ
https://paiza.jp/works/mondai/query_primer/query_primer__idl...N 人組のロボットアイドルグループのマネージャーとなった paiza 君は、グループに所属しているアイドル全員の名前を把握しておく必要があります。アイドルグループにはメンバーの加入と脱退がつきものなので、そのたびにメンバーを覚えたり忘れたりする必要があります。
paiza 君は仕事として握手会の度にアイドル全員の名前を書き出します。
ロボットの名前はほとんどが乱数的に付けられたものなので覚えるのが大変です。
そこで、イベント（メンバーの加入・脱退と握手会）が与えられるので、それらに伴う paiza 君の仕事をおこなうプログラムを作成しましょう。
N K
name_1
...
name_N
S_1
...
S_K・1 行目では、アイドルグループの初期メンバー数 N とイベントの回数 K が与えられます。
・続く N 行では、N 人の初期メンバーの名前が与えられます。
・続く K 行では、起こったイベントを表す文字列が時系列順に与えられます。
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N , K ≦ 100,000
・name_i はアルファベット小文字(a ~ z)と数字(0 ~ 9)から成る 20 文字以下の文字列です。 (1 ≦ i ≦ N)
・S_i (1 ≦ i ≦ K) は次のいずれかの形式で与えられます。
・join name
name という名前のアイドルが加入することを表します。
name はアルファベット小文字(a ~ z)と数字(0 ~ 9)から成る 20 文字以下の文字列です。
・leave name
name という名前のアイドルが脱退することを表します。
name はアルファベット小文字(a ~ z)と数字(0 ~ 9)から成る 20 文字以下の文字列です。
脱退時に name という名前のアイドルがグループにいることが保証されています。
・handshake
握手会がおこなわれることを表します。
握手会時点でのグループの全メンバーの名前を辞書順に改行区切りで出力してください。
グループのメンバーが 0 人であるときには何も出力しないでください。
・アイドルグループに所属するメンバーの名前は重複しないことが保証されています。
・握手会がおこなわれるのは 10 回以下であることが保証されています。
入力例
2 7
nene
ao
handshake
leave nene
join neko
join koko
handshake
leave neko
handshake出力例
ao
nene
ao
koko
neko
ao
kokoロボットアイドルグループって何ぞや！？ そして、最大で 20 万人になるらしい。三重県鈴鹿市、大阪府岸和田市あたりが 20 万人都市らしいです。
Python
N,K = map(int,input().split())
A = { input() for _ in range(N) }
for _ in range(K):
S = input().split()
event = S[0]
if event == 'handshake':
for name in sorted(A):
print(name)
else:
name = S[1]
if event == 'join':
A.add(name)
else:
A.remove(name)VBA
Sub query_primer__idle_group()
NK = Split(Cells(1, 1), " ")
N = Val(NK(0))
k = Val(NK(1))
Dim dic As Object
Set dic = CreateObject("Scripting.Dictionary")
For i = 1 To N
name = Cells(i + 1, 1)
dic.Add name, name
Next
For i = 1 To k
s = Split(Cells(i + N + 1, 1), " ")
eve = s(0)
If eve = "handshake" Then
If dic.Count > 0 Then
arrKeys = dic.Keys
Dim arrList()
ReDim arrList(dic.Count - 1, 1)
For j = LBound(arrKeys) To UBound(arrKeys)
arrList(j, 0) = arrKeys(j)
arrList(j, 1) = dic(arrKeys(j))
Next
Call QuickSort_dic(arrList, LBound(arrList, 1), UBound(arrList, 1))
dic.RemoveAll
For j = LBound(arrList) To UBound(arrList)
dic.Add arrList(j, 0), arrList(j, 1)
Next
For Each v In dic
Debug.Print v
Next
End If
Else
name = s(1)
If eve = "join" Then
dic.Add name, name
Else
dic.Remove name
End If
End If
Next
End Sub
Private Sub QuickSort_dic(ByRef arrList() As Variant, ByVal minIDX As Long, ByVal maxIDX As Long)
Dim valMEDIAN As Variant
Dim arrTEMP() As Variant
Dim i As Long
Dim j As Long
'ソート範囲の上下限を設定
i = minIDX
j = maxIDX
'基準値としてインデックスの中央値のデータを使用します。
valMEDIAN = arrList(Int((minIDX + maxIDX) / 2), 0)
Do
'インデックスの小さい方から値を比較していく
Do While StrComp(arrList(i, 0), valMEDIAN) < 0
i = i + 1
Loop
'インデックスの大きい方から値を比較していく
Do While StrComp(arrList(j, 0), valMEDIAN) > 0
j = j - 1
Loop
'インデックスが逆転したらループ抜け
If i >= j Then Exit Do
'配列を定義
ReDim arrTEMP(0, 1)
'配列内のデータの入れ替え１
arrTEMP(0, 0) = arrList(i, 0)
arrList(i, 0) = arrList(j, 0)
arrList(j, 0) = arrTEMP(0, 0)
'配列内のデータの入れ替え２
arrTEMP(0, 1) = arrList(i, 1)
arrList(i, 1) = arrList(j, 1)
arrList(j, 1) = arrTEMP(0, 1)
'配列の初期化
Erase arrTEMP
'インデックスの加減算
i = i + 1
j = j - 1
Loop
'再帰でソートが完了するまで繰り返し
If (minIDX < i - 1) Then Call QuickSort_dic(arrList, minIDX, i - 1)
If (maxIDX > j + 1) Then Call QuickSort_dic(arrList, j + 1, maxIDX)
End Subいつもの如く、paiza の境界値データを用いたテストでは、Debug.print で dic.count だけ出力されるように変更すると、約 21 秒で完了（このままだと約 480 秒）。配列を用いたパターンは途中でメモリ不足で止まりました。
最後に
Python の set って凄いですね。VBA でテストした境界値データが 1 秒以内で完了します。VBA はローカルの環境依存なので、参考値程度です。
計算量を意識することで、過去に書いたコードの無駄に気づくことが多いです。特に AWS Lambda は従量課金であるため、少しでも早いコードに書き換えることができれば、それだけ課金額を抑えることが出来るようになります。
引き続き、よろしくお願いいたします！