ABC155 C - Poll から学んだ

3912 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク

何か辞書で行けないかな？
とりあえずサンプルを見てみる

辞書で各要素をカウント。
=> 最大値を取り出して
=> 辞書順に最大値に合うものを print する。

辞書を key / item で一回ずつソートすれば行けるんじゃね？

=> 最大値を取り出して ...item でソート
=> 辞書順に最大値に合うものを print する。...key を辞書順でソート

調べたらスグに出てきた、神。

早速かいてみる。

Poll.py
N = int(input())
dic = {}

for _ in range(N):#O(n)
    s = input()
    if s not in dic:
        dic[s] = 0
    dic[s] += 1

#item についてソート。
lis = sorted(dic.items(),key=lambda t:t[1])#O(nlogn)
ref = lis[-1][1]#最大値とりだし

#key を辞書順に並び替え
lis = sorted(dic.items(),key=lambda t:t[0])#O(nlogn)
print(lis)

for a,b in lis:#O(n)
    if b == ref:
        print(a)

計算量はトータル O(n) x 2set + O(nlogn) x 2set だから、
8*10^5 っと言ったところだろうか。
一応通った。