第102回【Python】辞書データの順序、辞書

現在取り組んでいるのは、paiza ラーニング問題集「C ランクレベルアップメニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 102 回目です。

102 回続けて、ゼロから勉強してみよう、と書くのもどうかと思っています。30 回目くらいから。最初のテーマが「ゼロから勉強してみよう」だったので、今更変えるのもおかしいかなと思いつつ、どこかで急に変えてしまうかもしれません。

それでは、今日も頑張ってみようと思います。

辞書データの順序

n 人の人の名前 s_1, …, s_n が与えられたのち、 m 回の「攻撃」に関する情報が与えられます。各行は “p_i a_i” というフォーマットで与えられ、 p_i はダメージを受けた人の名前 （s_1, …, s_n のいずれか） 、 a_i は p_i が受けたダメージ数を表す数です。なお、一度もダメージを受けていない人の合計ダメージは 0 とします。

それぞれの人が受けた合計ダメージを、人の名前のアルファベットの辞書順に出力してください。

n
s_1
...
s_n
m
p_1 a_1
...
p_m a_m

1 行目には正整数 n が与えられ、 2 行目から (n + 1) 行目には人の名前 s_1, …, s_n が改行区切りで与えられます。 (n + 2) 行目には正整数 m が与えられ、 (n + 3) 行目から (n + m + 2) 行目には人の名前 p_i （s_1, …, s_n のいずれか） とその人が受けたダメージ a_i が “p_i a_i" という半角スペース区切りのフォーマットで m 行与えられます。

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≤ n , a_i ≤ 50 （1 ≤ i ≤ n）
・各 s_i （1 ≤ i ≤ n） はアルファベット大文字からなる長さ 1 以上 50 以下の文字列で、互いに全て異なる

入力例

2
MIDORIKAWA
KIRISHIMA
2
KIRISHIMA 1
KIRISHIMA 2

出力例

3
0

単純にソートすると、リスト型で要素がタプルになります。Python だと、そのまま抜き出すことができるので良い感じです。

Python
N = int(input())
dic = { input():0 for _ in range(N) }
M = int(input())
for _ in range(M):
    p,a = input().split()
    dic[p] += int(a)
dic = sorted(dic.items())
for k,v in dic:
    print(v)
VBA
Private Sub c_rank_dictionary_step3()

    N = Cells(1, 1)
    Dim dic As Object
    Set dic = CreateObject("Scripting.Dictionary")
    For i = 1 To N
        p = Cells(i + 1, 1)
        dic.Add p, 0
    Next
    M = Cells(N + 2, 1)
    For i = 1 To M
        PA = Split(Cells(i + N + M, 1), " ")
        dic(PA(0)) = dic(PA(0)) + Val(PA(1))
    Next
    arrKeys = dic.keys
    Dim arrList()
    ReDim arrList(dic.Count - 1, 1)
    For i = LBound(arrKeys) To UBound(arrKeys)
        arrList(i, 0) = arrKeys(i)
        arrList(i, 1) = dic(arrKeys(i))
    Next
    Call QuickSort_dic(arrList, LBound(arrList, 1), UBound(arrList, 1))
    dic.RemoveAll
    For i = LBound(arrList) To UBound(arrList)
        dic.Add arrList(i, 0), arrList(i, 1)
    Next
    arrKeys = dic.keys
    For Each v In dic
        Debug.Print dic.Item(v)
    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

辞書

p 人のグループ A , q 人のグループ B , r 人のグループ C があります。各グループのメンバーにはそれぞれ番号がつけられており、 A グループの i 番目の人は B グループの j 番目の人に仕事を任せ、 B グループの j 番目の人は与えられた仕事を C グループの k 番目の人に任せます。すると結局、 A グループの i 番目の人の仕事をするのは C グループの k 番目の人だということになります。

パイザ君は A グループの各人の仕事を結局 C グループの誰が行うことになるのか知りたがっています。 A グループの人のそれぞれが最終的に C グループの誰に仕事を頼むことになるのかを、 A グループの人の番号が小さい順に p 行出力してください。

p q r
i_1 j_1
...
i_p j_p
j'_1 k_1
...
j'_q k_q

1 行目には A グループ、 B グループ、 C グループのそれぞれの人数 p , q , r が半角スペース区切りで与えられます。
2 行目から (p + 1) 行目までは A グループの人の番号とその人が仕事を頼む B グループの人の番号 i_a, j_a （1 ≤ a ≤ p） が半角スペース区切りで、 (p + 2) 行目から (p + q + 2) 行目までは B グループの人の番号とその人が仕事を頼む C グループの人の番号 j’_b , k_b （1 ≤ b ≤ q） が半角スペース区切りで与えられます。

すべてのテストケースにおいて、以下の条件をみたします。

・1 ≤ p , q , r ≤ 50
・1 ≤ i_a ≤ p , 1 ≤ j_a , j’_b ≤ q , 1 ≤ k_b ≤ r （1 ≤ a ≤ p , 1 ≤ b ≤ q）
・各 i_a は全て異なる
・各 j’_b は全て異なる

A グループから仕事を頼まれた B グループの人は必ずその仕事を C グループの誰かに頼みます。 B グループに関する入力には「余計な」ものも含まれます。すなわち、 A グループの誰からも仕事を頼まれていない B グループの人に関して、その人が C グループの誰に仕事を頼むかについての情報が与えられることもあります。

入力例

2 2 2
2 1
1 2
1 1
2 2

出力例

1 2
2 1

孫請けの誰がやったか知りたい？ なんかブラックな香りがするぞ。

Python
p,q,r = map(int,input().split())
dic_ab = {}
dic_ac = {}
for _ in range(p):
    a,b = map(int,input().split())
    dic_ab[b] = a
for _ in range(q):
    b,c = map(int,input().split())
    if b in dic_ab:
        dic_ac[dic_ab[b]] = c
dic_ac = sorted(dic_ac.items())
for k,v in dic_ac:
    print(k,v)
VBA
Private Sub c_rank_dictionary_boss()

    rowcnt = 1
    PQR = Split(Cells(rowcnt, 1), " ")
    rowcnt = rowcnt + 1
    Dim dic As Object
    Set dic_AB = CreateObject("Scripting.Dictionary")
    Set dic = CreateObject("Scripting.Dictionary")
    For i = 1 To PQR(0)
        AB = Split(Cells(rowcnt, 1), " ")
        rowcnt = rowcnt + 1
        dic_AB.Add AB(1), AB(0)
    Next
    For i = 1 To PQR(1)
        BC = Split(Cells(rowcnt, 1), " ")
        rowcnt = rowcnt + 1
        If dic_AB.exists(BC(0)) Then
            dic.Add dic_AB(BC(0)), BC(1)
        End If
    Next
    arrKeys = dic.keys
    Dim arrList()
    ReDim arrList(dic.Count - 1, 1)
    For i = LBound(arrKeys) To UBound(arrKeys)
        arrList(i, 0) = arrKeys(i)
        arrList(i, 1) = dic(arrKeys(i))
    Next
    Call QuickSort_dic(arrList, LBound(arrList, 1), UBound(arrList, 1))
    dic.RemoveAll
    For i = LBound(arrList) To UBound(arrList)
        dic.Add arrList(i, 0), arrList(i, 1)
    Next
    arrKeys = dic.keys
    For Each v In dic
        Debug.Print v & " " & dic.Item(v)
    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

最後に

VBA で書くのがきつくなりつつありますが、まぁ、出来るところまでは頑張るつもりです。

ただ、模範解答と照らし合わせると、どちらがスマートなのかは微妙なところ。気になる方は、是非、paiza でご確認ください。速度的には LeoSaki（旦那）が書いた方が出ると思うのだけれど。うーん。

引き続き、よろしくお願いいたします！

Python学習,Python,paiza

Posted by LeoSaki