Pythonでリスト内のすべての値を同じにするために必要な最小操作回数を求めるプログラム

問題の概要

整数のリスト nums が与えられたとき、次の操作を実行できます。「リスト内の最大の数を選び、それを2番目に大きい数へ変換する」というものです。この操作を繰り返して、リスト内のすべての整数を同じ値に揃えるために必要な最小の操作回数を求めてください。

具体例で理解する

たとえば、入力が nums = [5, 9, 2] の場合、出力は 3 になります。手順は以下の通りです。

• まず最大値の 9 を選び、2番目に大きい 5 に変換 → 配列は [5, 5, 2] になる
• 次に 5 を選び、2番目に大きい 2 に変換 → [5, 2, 2] になる
• もう一度残りの 5 を選び、2 に変換 → [2, 2, 2] となり完成

解法のアプローチ

この問題は、各値が「ソート済みの一意な値リストの中で何番目に位置するか」に着目することで、シンプルかつ効率的に解けます。ある値が最終的な最小値に到達するまでには、その値より大きい一意な値の個数だけ段階的な変換が必要になるためです。

具体的な手順は次の通りです。

• vals: nums 内の一意な値を取り出し、昇順にソートしたリストを作成する
• vtoi: 各値 v をキー、そのインデックス i を値とする辞書（マップ）を作成する
• nums 内のすべての要素 v に対する vtoi[v] の合計を返す

この方法では、時間計算量は O(n log n)（ソート処理が支配的）、空間計算量は O(n) となり、非常に効率的です。

実装例

class Solution:
   def solve(self, nums):
      vals = sorted(set(nums))
      vtoi = {v: i for i, v in enumerate(vals)}
      return sum(vtoi[v] for v in nums)

ob = Solution()
nums = [5, 9, 2]
print(ob.solve(nums))

入力

[5, 9, 2]

出力

3

まとめ

一意な値をソートしてインデックスを対応付けることで、各要素が最小値に到達するまでに必要な変換回数を簡単に集計できます。set による重複除去と enumerate を使った辞書構築の組み合わせは、Pythonならではの簡潔な書き方として覚えておくと便利です。