SetとListでいかに計算量が変わるか（Python）

解決したいこと

Pythonにおいて、Setを使う問題に当たりました。
しかし、下記問題では、そこまでSetを使っても持っているデータの個数が減るということもないように思います。

言い換えると、なぜSetを使うとListよりもそんなに早いんでしょうか、ということを解決したいです。

問題はAtcoderの下記問題になります。
https://atcoder.jp/contests/abc187/tasks/abc187_c

私がACしたコードは以下になります。

# 187c 
flag = False
ans = ""
n = int(input())
li = []
for _ in range(n):
    li.append(input())
# リストをセットに変換
sets = set(li)

for s in sets:
    if "!" + s in sets:
        ans = s
        flag = True
        break

if flag:
    print(ans)
else:
    print("satisfiable")

入力を受け取る時、リスト内包表記で書いてないのはスルーしてください、、

自分で試したこと

最初は受け取ったリストをそのままの形でin演算子を使い探索していました。
しかし、これだとPypyを使ってもTLEしてしまいます。
in演算子にも結構な計算量がかかるというのはなんとなく自覚していましたが、他の方法が思いつきませんでした。

解説を見ると、Setを使いましょうということだったのですが、今回の問題においてSetがそこまで計算量に影響があるのだろうかと疑問に思いました。
私の体感として、Setを使うのは持つデータに被りがあるときだと認識していたからです。

というわけで、この問題において、Setが必要とされる理由について詳しい方がいましたらご教授いただけますと幸いです。