C - Neo-lexicographic Ordering　記録

C - Neo-lexicographic Ordering

本日はこちらの問題をやりもうした。C問題といえど僕にとってはまだまだ難問。特訓も兼ねて挑戦させていただきました。

一応今回は自分の書いたコードでもACを叩き出すことが出来たので早速コード紹介。

dic = input().rstrip()
N= int(input())
nameList = [input() for _ in range(N)]
orderDic= {}
NameDic = {}
maxLength = 0

for i, d in enumerate(dic):
 orderDic[d] = i
 
for name in nameList:
 if maxLength < len(name):
   maxLength = len(name)

for i, name in enumerate(nameList):
 nameValue = 0
 for j, char in enumerate(name):
   nameValue += (orderDic[char]+1) * 100**(maxLength-j) 
 NameDic[nameValue] = name

NameDic = sorted(NameDic.items())

for nameInfo in NameDic:
 print(nameInfo[1])

やはり変数が多くなりがちで全体的にゴチャゴチャしております。いい加減簡潔なコードをかけるようにならなくては...

dic = input().rstrip()
N= int(input())
nameList = [input() for _ in range(N)]

ここの三行で入力情報を取り入れている感じです。
dicには26文字のアルファベット(順不同)、Nには入力される名前の数、nameListは入力された名前を格納した配列。

orderDic= {}
NameDic = {}
maxLength = 0

orderDicはアルファベットと数字が紐づけるための辞書、数字は順番を表している感じです。NameDicには、keyとして名前、valueとして最終的な順番を決めるための数値を入れる予定です。

for i, d in enumerate(dic):
 orderDic[d] = i

ここでアルファベットと数字を紐づける作業をしています。
例えば、入力された２６文字のアルファベットがabcdefg.......xyzという正規のアルファベット順だとすると、
orderDic = {a: 0, b: 1, c: 2, d: 3 , e: 4, f: 5, g: 6  以下略}　みたいな感じの辞書です。

for name in nameList:
 if maxLength < len(name):
   maxLength = len(name)

この処理は入力された名前の中で、最も長い文字列の文字数をmaxLengthに格納しているだけです。

for i, name in enumerate(nameList):
 nameValue = 0
 for j, char in enumerate(name):
   nameValue += (orderDic[char]+1) * 100**(maxLength-j) 
 NameDic[nameValue] = name

この作業では、名前をひとつずつ取り出して、さらにその名前から一文字ずつ取り出して、アルファベット順と、ある一文字がある名前の何文字目に位置するかを基に名前の重さを計算していく感じです。その後、NameDicにkeyをnameValue（名前の重さ）、valueにname（名前）を格納しています。

nameValueは、ある名前のある文字のアルファベット順が後ろであるほど、また、ある文字がある名前の前の方にあればあるほど、値がでかくなる感じです。

名前の重さという表現が分かりづらいと思いますが、ここでは名前の重さが小さいほど、名前の順番が前になると思っていてください。

NameDic = sorted(NameDic.items())

for nameInfo in NameDic:
 print(nameInfo[1])

最後のこの処理では、NameDicをkeyを基準に昇順に並べ替え、その後、NameDicの前から順番に名前を出力しています。

まだまだ非効率なコードだとは思いますが、とりあえずACという結果に満足して喜び勇んで記録しにきました。

以上です。