AtCoder-ABC219 C - Neo-lexicographic Ordering【Python解答例】

サイシードプログラミングコンテスト2021(AtCoder Beginner Contest219)のC問題についてPythonの解答例を記事にしていきます。
Sciseed Programming Contest 2021（AtCoder Beginner Contest 219） - AtCoder

AtCoder Beginner Contest219 C - Neo-lexicographic Ordering

C - Neo-lexicographic Ordering

問題文

AtCoder 王国を治める高橋君は、英小文字のアルファベット順を変更することにしました。

新たなアルファベット順はa , b ,…, z を並べ替えて得られる文字列 X を用いて表されます。X の i(1≤i≤26) 文字目は、新たな順番において i 番目に小さい英小文字を表します。

AtCoder 王国には N 人の国民がおり、それぞれの国民の名前は S 1​ ,S 2​ ,…,S N​ です。ここで、S i​ (1≤i≤N) は英小文字からなります。
これらの名前を、高橋君の定めたアルファベット順に基づく辞書順に従って並べ替えてください。

制約

・X は a , b ,…, z を並べ替えて得られる
・2 ≤ N ≤ 50000
・N は整数
・1≤∣S i​ ∣≤10 (1 ≤ i ≤ N)
・S i​ は英小文字からなる (1 ≤ i ≤ N)
・S i​ ≠ S j​ (1 ≤ i < j ≤ N)

解答例

x = input()

n = int(input())

S = []
for _ in range(n):
    S.append(input())

res = []
for i in range(n):
    tmp = ""
    for j in range(10):
        if j < len(S[i]):
            for k in range(26):
                if x[k] == S[i][j] and k <= 8:
                    tmp += "0"
                    tmp += str(k+1)
                    break
                elif x[k] == S[i][j] and k > 8:
                    tmp += str(k+1)
                    break
        else:
            tmp += "00"
    res.append([tmp,i])

res.sort()

for i in range(n):
    print(S[res[i][1]])

解説

アルファベット順をXに変更したときに、N人の名前を変更したアルファベット順に並び替える問題です。

新しいアルファベット順に並び替えるために、i番目の名前Siをアルファベット順に基づいた数字に変換しました。

名前のj文字目が、Xのk(1～9)番目の文字の場合は2桁分の0kをtmpに、それ以外ならそのままkを付け加えます。

名前の長さがばらばらでも10文字分まで処理して 配列resにtmpとインデックスを格納しました。

つぎにresをソートすることで辞書順に並び替えます。

並び替えたresのインデックスをもとにSを出力していくことでACできました。

ABC219の関連記事はこちら
ebisuke33.hatenablog.com