ABC219 C - Neo-lexicographic Ordering에서 배운




밟는다 밟는다.
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

좋은 웹페이지 즐겨찾기