Google APAC university test 2017 round AのA問題country leaderに挑戦する.
この問題は,
である. なお,空白文字は文字の種類数に含めない. また,この問題では使われている文字の種類数が最大の名前を「リーダー」としている.
入力と,それに対する正しい出力の例は
である.
"ADAM"に使われている文字は3種類,"BOB"に使われている文字は2種類,"JOHNSON"に使われている文字は5種類であるからである.
"A AB C"に使われている文字は3種類,"DEF"に使われている文字も3種類であるが,辞書順では"A AB C"の方が"DEF"よりも先だからである.
解答例として,名前を引数として文字の種類数を返す関数をdifferent letters,その関数を用いて問題を解く関数をsolveとして以下に定義する. このdifferent_lettersでは,名前に使われている文字の種類数を数えるために辞書を用いる.
def different_letters(name):
used_alphabets = {} # 文字の種類数を数えるための辞書を用意する.
for char in name: # 名前のそれぞれの文字に関して以下を繰り返す.
if char == ' ': # (問題の仮定より)空白文字ならば,
continue # 何も処理しない.
else: # そうでない(空白文字でない)ならば,
used_alphabets[char] = 1 # その文字が使われているしるしとして辞書の値を1にする.
return len(used_alphabets.keys()) # 辞書のキーの個数が,名前で使われている文字の種類数のはずである.
def solve(names):
max_letters = 0 # 最大文字種類数の最大値を覚えるための変数を用意する.
leader = '' # リーダーの名前を覚えるための変数を用意する.
for name in names: # すべての名前に関して以下を繰り返す.
diff_letters = different_letters(name) # まず,その名前で使われている文字の種類数を数える.
if max_letters < diff_letters: # その名前の文字の種類数が,それまでの最大値よりも大きいならば,
max_letters = diff_letters # その種類数を最大値として覚え直し,
leader = name # その名前をリーダーとする.
elif max_letters == diff_letters: # そうでなくて,その名前の種類数がそれまでの最大値と同じで,
if name < leader: # かつ,現時点でのリーダーの名前よりも辞書順で先ならば,
leader = name # その名前をリーダーとする.
return leader
Pythonでは,文字列を比較することは,辞書順の大小を比べることである. よって,このように簡潔に書ける.
実際にサンプルの入力を与えて,出力を確かめてみる.
solve(['ADAM', 'BOB', 'JOHNSON'])
'JOHNSON'
solve(['A AB C', 'DEF'])
'A AB C'
これだけのサンプルで判断するのは早計かも知れないが,とりあえず良さそうである.
続けて,上記の関数solveを用いて,入力のファイルを読み込み,出力のファイルを書き出す関数answerを以下に定義する
def answer(input_file_name, output_file_name):
input_file = open(input_file_name)
output_file = open(output_file_name, 'w')
T = int(input_file.readline())
for case_number in range(1, T + 1):
N = int(input_file.readline())
names = []
for n in range(N):
names += [input_file.readline().rstrip()]
output_file.write('Case #{0}: {1}\n'.format(case_number, solve(names)))
input_file.close()
output_file.close()
return # このreturnは必要ないが,お行儀よく一応付けておく.
Small datasetの入力ファイルをA-small-practice.in,large datasetの入力ファイルをA-large-practice.inとして以下を実行してみる.
answer('A-small-practice.in', 'A-small-practice.out')
answer('A-large-practice.in', 'A-large-practice.out')
出力ファイルA-small-practice.out,A-large-practice.outのいずれも正しいようだ.
上で定義した,名前(あるいは文字列)に含まれる文字の種類数を数える関数different_lettersでは辞書を使った.
しかし一方で,何かが「ある」か「ない」かを処理するだけならばPythonのデータ構造である集合も便利である. ここでは集合を紹介する.
Pythonの集合は,そのまま数学の集合を使えるデータ構造である. 以下に使用例を示す.
list_PP = ['pen', 'pineapple'] # まず,準備として文字列を要素とするリストを作る.
list_AP = ['apple', 'pen']
list_PPAP = ['pen', 'pineapple', 'apple', 'pen']
set_PP = set(list_PP) # 組込み関数setはリストを元に集合を作る.
set_AP = set(list_AP)
set_PPAP = set(list_PPAP)
set_PP
{'pen', 'pineapple'}
set_AP
{'apple', 'pen'}
set_PPAP
{'apple', 'pen', 'pineapple'}
set_PPAPは集合なので,要素'pen'は1つだけ残る.
そして,Pythonの集合は順番を区別しないので,要素はアルファベット順に並べ替えられて表示されている.
以下に幾つか集合の演算の例を示す.
set_PP | set_AP # 和集合の計算
{'apple', 'pen', 'pineapple'}
set_PP & set_AP # 共通部分の計算
{'pen'}
set_PP ^ set_AP # どちらかだけに含まれる要素の計算
{'apple', 'pineapple'}
set_PP - set_AP # set_PPに含まれ,set_APに含まれない要素の計算
{'pineapple'}
len(set_PPAP) # リストと同様に要素数は組込み関数lenでわかる.
3
他にも集合の演算はあるが,より詳しくはネットなどで調べていただきたい.
この集合を用いると,上記のdifferent_lettersはもっと簡潔に定義できる.
以下にdifferent_lettersを再定義する.
def different_letters(name):
return len(set(name) - set([' ']))
一行で書けてしまうので,実は関数として定義する必要はなかったかもしれない.
一応解説すると,
solveとanswerを再定義して動作を試してみる.
def solve(names): # 上での定義と全く同じである.
max_letters = 0 # 最大文字種類数の最大値を覚えるための変数を用意する.
leader = '' # リーダーの名前を覚えるための変数を用意する.
for name in names: # すべての名前に関して以下を繰り返す.
diff_letters = different_letters(name) # まず,その名前で使われている文字の種類数を数える.
if max_letters < diff_letters: # その名前の文字の種類数が,それまでの最大値よりも大きいならば,
max_letters = diff_letters # その種類数を最大値として覚え直し,
leader = name # その名前をリーダーとする.
elif max_letters == diff_letters: # そうでなくて,その名前の種類数がそれまでの最大値と同じで,
if name < leader: # かつ,現時点でのリーダーの名前よりも辞書順で先ならば,
leader = name # その名前をリーダーとする.
return leader
def answer(input_file_name, output_file_name): # 上での定義と全く同じである.
input_file = open(input_file_name)
output_file = open(output_file_name, 'w')
T = int(input_file.readline())
for case_number in range(1, T + 1):
N = int(input_file.readline())
names = []
for n in range(N):
names += [input_file.readline().rstrip()]
output_file.write('Case #{0}: {1}\n'.format(case_number, solve(names)))
input_file.close()
output_file.close()
return # このreturnは必要ないが,お行儀よく一応付けておく.
answer('A-small-practice.in', 'A-small-practice.out')
answer('A-large-practice.in', 'A-large-practice.out')
ファイルA-small-practice.out,A-large-practice.outのいずれも正しく出力される.