ABC219 C - Neo-lexicographic Ordering에서 배운
8577 단어 AtCoder파이썬AtCoderBeginnerContest
밟는다 밟는다.
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
Reference
이 문제에 관하여(ABC219 C - Neo-lexicographic Ordering에서 배운), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/AKpirion/items/58805158dc6bdfb3eeae텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)