Pythonプログラム：集合の要素をチェックして幸福度を求める方法

問題の概要

n個の異なる整数からなる配列 nums があるとします。さらに、互いに共通要素を持たない2つの集合 A と B も与えられています。

ここで「幸福度（happiness）」というパラメータを用意し、初期値は0とします。配列 nums 内の各整数 i を順番に調べながら、次のルールに従って幸福度を更新していきます。

• i が集合 A に含まれている場合 → 幸福度を +1 する
• i が集合 B に含まれている場合 → 幸福度を -1 する

すべての要素を処理し終えた後の、最終的な幸福度の値を求めるのがこの問題の目的です。

具体例

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

• nums = [1, 2, 5, 8, 6, 3]
• A = {5, 8, 9, 7, 3}
• B = {2, 4, 12, 15}

このとき出力は 2 になります。理由は以下の通りです。

• 5、8、3 は A に含まれるため、幸福度は +3 される
• 2 は B に含まれるため、幸福度は -1 される
• 結果として、最終的な幸福度は 3 − 1 = 2 となる

解決の手順

この問題は、以下のステップで解くことができます。

1. 幸福度を 0 で初期化する
2. 配列 nums 内の各要素 i について順に処理する
   • i が A に含まれている場合、幸福度を 1 増やす
   • そうでなく i が B に含まれている場合、幸福度を 1 減らす
3. 最終的な幸福度の値を返す

なお、Pythonの set（集合）はハッシュテーブルで実装されているため、要素の存在確認（in 演算子）は平均 O(1) で行えます。そのため、このアルゴリズム全体の計算量は O(n) となり、非常に効率的です。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums, A, B):
   happiness = 0
   for i in nums:
      if i in A:
         happiness += 1
      elif i in B:
         happiness -= 1
   return happiness

nums = [1,2,5,8,6,3]
A = {5,8,9,7,3}
B = {2,4,12,15}
print(solve(nums, A, B))

入力

[1,2,5,8,6,3], {5,8,9,7,3}, {2,4,12,15}

出力

2

まとめ

このプログラムでは、配列の各要素を集合 A・B と照合しながら幸福度を加減算することで、最終的な幸福度を簡単に計算できます。set を使った存在確認は高速なので、大量のデータを扱う場合でも安心して利用できるアプローチです。