AtCoder Beginner Contest 073CをPythonで解く

今回は、AtCoder Beginner Contest 073Cを解いていきたいと思います。

問題文

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

こう考えた

• 空の配列Lを作成
• forで配列Lに要素が無ければappend
• forで配列Lに要素があればremove
• len(L)で答えを出力

🐍for1つしか使ってないイケてるコードが書けそうや

実際書いたコード

N=int(input())
L=[]
for i in range(N):
  A=int(input())
  if A in L:
    L.remove(A)
  else:
    L.append(A)
print(len(L))

結果

TLE

🐍for1つしか使ってないのになんでや！

解説を元に考え直す。

Aをソートすると、同じ数が隣り合うように並べ替えられる。

これを左か順にみていくと、奇数回登場する数が何種類あるかを数えることができる。

🐍実装してみよ。

書いたコード

N=int(input())
L=[]
for i in range(N):
  L.append(int(input()))
ans=0
for i in set(L):
  if L.count(i)%2==1:
    ans=ans+1
print(ans)

結果

TLE

🐍まじかよ。。

ListからSetに変えてみる

🐍set早いってまじかよ。。

書いたコード

n = int(input())
s = set()
for i in range(n):
  a = input()
  if a in s:
    s.remove(a)
  else:
    s.add(a)
print(len(s))

結果

AC

🐍まじかよ。。

🐍set()はList()より早い。覚えた。