AtCoderで公開されている、E869120さんの『競プロ典型90問』を解いていきます。
問題
$N$件のユーザー登録申請に対して、そのユーザーが存在しなければ申請が承諾される。承諾される申請の番号を求める。
アイデア
登録しているユーザーの情報（ユーザー名）を保管する変数を作る必要あり
⇒リスト、セット、辞書などがある。
- リスト：各ユーザーの登録順の情報を保管できるが、
inの計算量は$O(n)$ - セット：登録順は保管できないが、
inの計算量は$O(1)$ - 辞書：ユーザー名をkey、ユーザーの登録日やrate等の他の情報をvalueとして保管できる
この問題においては順番は関係なく、登録しているユーザー名の一覧があって検索ができればよいので、セットを使う。
set型について
-
set()で初期化！（{}は辞書） - set型は重複する要素をもたない
-
B = set(A)でリストAから重複を省いたセットBを作ることができる（順番の情報は破棄される） - 和集合、差集合、積集合などの演算子が使える
a = {0, 2, 4, 6, 8}
b = {0, 3, 6, 9}
wa = a | b
sa = a - b
seki = a & b
print(wa)
print(sa)
print(seki)
# 出力
# {0, 2, 3, 4, 6, 8, 9}
# {8, 2, 4}
# {0, 6}
なお、リストからセットを作る際には$O(n)$の計算量が必要であるため、セットにしてから検索すれば計算量が小さくなる、ということはありません。
最終的な実装例
N = int(input())
users = set()
for i in range(N):
name = input()
if name not in users:
print(i + 1)
users.add(name)
だんだんAtCoderの問題に慣れてきた気がします。以前の僕なら何も考えずにリストを使って（おそらく）時間超過になっていたでしょう。これからもイテレータの選択には注意していきます。
お読みいただきありがとうございました！
参考記事