ABC073 C問題のTLEについて

Question

前提・実現したいこと

C問題でTLEが出て改善しようとしましたがうまくいきません。
助けてください

問題

あなたは、joisinoお姉ちゃんと以下のようなゲームをしています。

最初、何も書いていない紙がある。
joisinoお姉ちゃんが一つの数字を言うので、その数字が紙に書いてあれば紙からその数字を消し、書いていなければその数字を紙に書く。これを
N
回繰り返す。
その後、紙に書かれている数字がいくつあるかを答える。
joisinoお姉ちゃんが言った数字が、言った順番に
A1
,
.
.
.
,
AN
として与えられるので、ゲーム終了後に紙に書かれている数字がいくつあるか答えてください。

発生している問題・エラーメッセージ

TLE

該当のソースコード

n = int(input())
nums = []
for i in range(n):
  num = int(input())
  nums.append(num)
count = 0
setnums = set(nums)
for j in setnums:
  test = nums.count(j)
  if test % 2 == 1:
    count += 1
print(count)

試したこと

setで多少改善しました。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

list.count() は、リストの全要素を1つずつ指定した値かどうか調べていき、個数をカウントしていくので、要素数が多い場合はそれに比例して時間がかかってしまいます (O(n))。
要素のアクセスが O(1) である dict を利用して、input() で読み込む段階で各値をカウントしていくとよいと思います。

以下のコードで通りました。

from collections import defaultdict

cnt = defaultdict(int)  # 各値の出現回数をカウントするための dict

n = int(input())
for i in range(n):
    value = int(input())
    cnt[value] += 1  # value の数を +1

ret = 0
for c in cnt.values():
    if c % 2 == 1:
        ret += 1  # 出現回数が奇数
print(ret)