Pythonで連絡先メールアドレスのリストからユニークな人数を求める方法

問題の概要

連絡先リストとして、メールIDのリストが与えられているとします。各行には、同じ人物のメールIDが複数含まれていることがあります。連絡先 i は、j < i を満たす任意の j について、連絡先 j が i と共通のメールアドレスを持つ場合に「重複」とみなされます。ここでの目的は、連絡先リストの中に何人のユニークな人物が存在するかを求めることです。

たとえば、入力が以下のような場合を考えてみましょう。

contacts = [["alex@gmail.com", "alex@yahoo.com"], ["alex_25@yahoo.com", "alex@gmail.com"], ["bob15@gmail.com"]]

この場合の出力は 2 になります。1番目と2番目の連絡先は同じメールアドレス（alex@gmail.com）を共有しているため同一人物と判断され、結果としてユニークな人物は2人になるからです。

解決のアプローチ

この問題は、これまでに出現したメールアドレスを記録しておくことで効率的に解けます。具体的には、以下の手順に従います。

• カウンター ans を 0 で初期化する
• 発見済みのメールアドレスを格納するセット found を用意する
• contacts 内の各連絡先 c について以下を繰り返す
  • フラグ duplicate を False で初期化する
  • c 内の各メールアドレス email について以下を判定する
    • email が found に存在しない場合は、found に追加する
    • すでに存在する場合は、duplicate を True にする
  • duplicate が False のままなら、ans を 1 増やす（新しい人物と判断）
• 最後に ans を返す

Pythonのセット（set）は要素の追加や存在確認を平均 O(1) で行えるため、メールアドレスの総数を N とすると、全体の計算量は O(N) になります。非常に効率的なアプローチです。

実装例

それでは、Pythonでの実装を見てみましょう。

def solve(contacts):
    ans = 0
    found = set()

    for c in contacts:
        duplicate = False

        for email in c:
            if email not in found:
                found.add(email)
            else:
                duplicate = True
        if not duplicate:
            ans += 1

    return ans

contacts = [
["alex@gmail.com", "alex@yahoo.com"],
["alex_25@yahoo.com", "alex@gmail.com"],
["bob15@gmail.com"]
]
print(solve(contacts))

入力

[["alex@gmail.com", "alex@yahoo.com"],
["alex_25@yahoo.com", "alex@gmail.com"],
["bob15@gmail.com"]]

出力

2

まとめ

このプログラムでは、セットを使って既出のメールアドレスを管理することで、各連絡先が新しい人物かどうかを効率的に判定しています。メールアドレスが1つでも過去の連絡先と一致すれば同一人物とみなし、すべてのメールアドレスが初登場である連絡先だけをカウントすることで、ユニークな人数を正確に求めることができます。