Atcoder典型90問027(★2)[in][listとset]

027 - Sign Up Requests （★2）

■要約

　解き方はすぐに思いついた．でてきた単語をリストに入れていって毎回の入力で得た単語がそのリストの中に入っているか確かめていけば良いと考えた．しかし，pythonではlist型におけるinの平均計算量はO(N)のため，毎回のループでこれを行うとO(N^2)の計算量が必要になりTLEとなってしまう．これを防ぐ方法は案外簡単で，set型を用いればよい．setは同じ値の重複を許さないような型なので，inの平均計算量がO(1)で済む．素晴らしい．

N = int(input())
temp = set()
for i in range(1, N+1):
 S = str(input())
 if S in temp: #setだとこの平均計算量がO(1)になる．listだとO(N)
   continue
 else:
   temp.add(S)
   print(i)