ABC解説

【pythonでABC155を解説】C - Poll

問題概要

問題ページ

C - Poll
C - Poll

問題ページへ移動する

問題文

\(N\) 枚の投票用紙があり、\(i\ (1 \leq i \leq N)\) 枚目には文字列 \(S_i\) が書かれています。

書かれた回数が最も多い文字列を全て、辞書順で小さい順に出力してください。

制約

  • \(1 \leq N \leq 2 \times 10^5\)
  • \(S_i\) は英小文字のみからなる文字列 \((1 \leq i \leq N)\)
  • \(S_i\) の長さは \(1\) 以上 \(10\) 以下 \((1 \leq i \leq N)\)

問題の考察

pythonで同一要素数をカウントする場合には、collections.Counter()が便利です。

カウントしたい要素のリストをcollections.Counter()に渡すと、要素をKey、要素数をValueとしたDict（辞書）型を返します。

この問題では、「書かれた回数が最も多い文字列を全て、辞書順で小さい順に出力してください。」とあります。

辞書型のままだとsort()が使えないので、collections.Counter().most_common()を使っています。（collections.Counter().items()だと並び替えできないみたいです。）

s.sort(key=lambda x: x[0])
s.sort(key=lambda x: x[1], reverse=True)

で「書かれた回数が多い順、辞書順で小さい順」に並び替えています。
最後に、最も多い出現回数の要素を順番に出力すれば良いです。（if v == s[0][1]ここで出現回数を確認しています。sは出現回数が多い順にソートされています。）

ACコード

import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    s = collections.Counter([str(readline().rstrip().decode('utf-8')) for _ in range(n)]).most_common()
    s.sort(key=lambda x: x[0])
    s.sort(key=lambda x: x[1], reverse=True)
    for k, v in s:
        if v == s[0][1]:
            print(k)
        else:
            break


if __name__ == '__main__':
    solve()

-ABC解説
-