DOJ Starter Contest 1 F - 문자열 정렬하기
- サイト
- DOJ
- コンテスト
- DOJ Starter Contest 1
- 問題
- F - 문자열 정렬하기
英小文字からなる 個の文字列が与えられます。文字列のスコアを、各文字の出現回数の二乗の和とします。例えば abaca のスコアは です。
次の優先順位で文字列を並べ、 行に つずつ出力する問題です(、各文字列の長さは 以下)。
- スコアが小さい順
- 長さが短い順
- 辞書順
同じ文字列も、与えられた個数だけ出力します。
各文字列について、Counter で文字ごとの出現回数を数え、その二乗を足せばスコアを求められます。
あとは、ソートのキーとして (スコア, 長さ, 文字列) というタプルを返します。Python はタプルを先頭の要素から順に比較するので、問題で指定された優先順位をそのまま表せます。
S.sort(key=q) では各文字列に対して q が 回ずつ呼ばれ、その結果を使ってソートします。最大文字列長を とすると、キーの計算に 、文字列の比較も含めたソートに かかります。
Python
from collections import Counter
N = int(input())S = [input() for i in range(N)]
def q(s): c = Counter(s) return (sum(i**2 for i in c.values()), len(s), s)
S.sort(key=q)for s in S: print(s)