ABC219 C - Neo-lexicographic Ordering から学んだ

9008 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク


踏む踏む。
S に含まれる英小文字を X の中から探し、
数字に置き換えてみた。だがしかし WA.

Neo-lexicographicOrdering_rv0.py
X = input()
N = int(input())

S =[]
dic = {}
for _ in range(N):#5*10**4
    s = input()
    y = ""
    for i in range(len(s)):#10
        y += str(X.index(s[i]))# index って 計算量は X 長に依存だなー 26
    dic[y] = s

#print(dic)
dic = sorted(dic.items(),key=lambda t:t[0])
#print(dic)

for a,b in dic:
    print(b)

数字を連結するのは良かったが、
例えば 1 , 2, 3 は 123 でよい。
しかし 1, 20 , 3 はどうなる？
1203 は正しく辞書順にできないのでは？

っというわけで、数字に置き換えるのではなく、
従来の abcdefghi... の順番に置き換えて考えたら通った。

Neo-lexicographicOrdering_rv1.py
Y = "abcdefghijklmnopqrstuvwxyz"
X = input()
N = int(input())

S =[]
dic = {}
for _ in range(N):#5*10**4
    s = input()
    y = ""
    for i in range(len(s)):#10
        for j in range(len(X)):#26
            if s[i] == X[j]:
                y += Y[j]
    dic[s] = y

#print(dic)
dic = sorted(dic.items(),key=lambda t:t[1])
#print(dic)

for a,b in dic:
    print(a)
#1774ms

計算量は余裕のはずだったが、実際はギリギリだった。
もうちょい考えてみるか。
index を使えば、もう少し簡略化できると思った。

abc219c.py
def solv():
    ref = "abcdefghijklmnopqrstuvwxyz"
    X = input()
    N = int(input())
    lis = []
    for _ in range(N):
        S = input()
        T = ""
        for i in range(len(S)):
            T += ref[X.index(S[i])]
        lis.append([S,T])
    lis = sorted(lis,key=lambda t:t[1])
    for a,b in lis:
        print(a)
solv()#232ms