Day 002-Q5 | 辞書・集合

問題

N 個の文字列が与えられる。各文字列が何回登場するかを、登場回数が多い順に出力せよ。登場回数が同じ場合は、辞書順で早い方を先に出力せよ。

入力形式

N
s_1
s_2
...
s_N

制約

$1 \le N \le 10^5$

各文字列の長さ ≤ 20

英小文字のみ

入出力例

入力例 1

7
apple
banana
apple
cherry
banana
apple
cherry

出力例 1

apple 3
banana 2
cherry 2

ヒント (段階的開示)

ヒント1: 方向性

Python の dict や collections.Counter で出現回数を数える。

ヒント2: アプローチ

Counter で頻度を数え、(-頻度, 文字列) でソートすると「頻度降順・同頻度なら辞書順」を一度に実現。

ヒント3: 誘導

from collections import Counter

counter = Counter(strings)
sorted_items = sorted(counter.items(), key=lambda x: (-x[1], x[0]))
for word, cnt in sorted_items:
    print(word, cnt)

模範解答 (Python)

from collections import Counter

N = int(input())
strings = [input() for _ in range(N)]

counter = Counter(strings)

sorted_items = sorted(counter.items(), key=lambda x: (-x[1], x[0]))

for word, cnt in sorted_items:
    print(word, cnt)

Step-by-Step 解説

1Counter で頻度カウント
Counter(list) で各要素の出現回数を自動でカウント。

2複数キーでのソート
key=lambda x: (-x[1], x[0]): -x[1] で頻度降順、x[0] で文字列を辞書順昇順。タプルは左から順に比較。

3結果の出力
for word, cnt in sorted_items: print(word, cnt)

計算量

Counter 構築: $O(N)$
ソート: $O(K \log K)$（K = ユニーク文字列数）
合計: $O(N \log N)$

よくあるミス

ミス	原因	正しい書き方
`key=lambda x: x[1]`	降順にならない	`key=lambda x: (-x[1], x[0])`
`.items()` を直接ループ	順序が保証されない	`sorted()` を使う
`counter[key]` 直接アクセス	KeyError	`get(key, 0)` or Counter

Day 002-Q5 — 辞書・集合

問題