Python collections の Counterオブジェクト

下記の問題を解きます。

kamipeipaa君は新しいものが大好きです。
kamipeipaa君はある日N個の整数A1,A2,A3,....,ANを見つけました。
整数Aiに対して，Ai=Ajとなるjがi以外に存在しなければ，Aiは新規性があるのではないかとkamipeipaa君は考えました。
上記の条件を満たす整数がいくつあるかkamipeipaa君に教えてあげてください。

No.182 新規性の虜 - yukicoder

素直にプログラムを書くと、

n = int(input())
a = list(map(int, input().split()))
print(sum(1 for i in set(a) if a.count(i) < 2))

計算量: O(n²)
これだとTLEになりました。
count()関数でO(n)の計算量が必要なので、非効率だったのです。
そこで
↓

n = int(input())
a = list(map(int, input().split()))
dic = dict()
for i in a:
    if i in dic:
        if dic[i]:
            dic[i] = False
    else:
        dic[i] = True
print(sum(1 for i in dic if dic[i]))

計算量: O(n)
としました。 これだと、1度リストaを走査すれば済みます。

ただ、これだと不恰好なので、collectionsのCounterオブジェクトを使って整形します。 Counterは、要素を辞書のキーとして保存し、そのカウントを辞書の値として保存するコレクションです。

# 例
from collections import Counter
b = [1, 1, 2, 3, 3]
Counter(b)
> Counter({1: 2, 3: 2, 2: 1})

これを使うと

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
print(sum(1 for i in Counter(a).values() if i < 2))

計算量: O(n)

↓もう少し工夫して

from collections import Counter
input()
print(sum( i < 2 for i in Counter(input().split()).values()))

計算量: O(n)
で、すっきりしましたね。