Pythonで1つのリストを別のリストへ変換するのに必要なスワップ回数をカウントするプログラム

問題の概要

2つの数値リスト L1 と L2 があるとします。各リストの長さは n で、すべての値はリスト内で一意であり、値の範囲は 0 ～ n-1 です。このとき、L1 を L2 に変換するために必要な「隣接要素のスワップ（交換）」の最小回数を求めます。

例えば、入力が L1 = [0, 1, 2, 3]、L2 = [2, 0, 1, 3] の場合、出力は 2 になります。まず 1 と 2 を入れ替えると L1 は [0, 2, 1, 3] になり、次に 0 と 2 を入れ替えると L1 は [2, 0, 1, 3] となり、L2 と一致するためです。

解決のアプローチ

この問題は、以下の手順で解くことができます。

• 答えを格納する変数 ans を 0 で初期化します。
• L2 の各要素 req について、次の処理を順に行います。
  • L1 内での req のインデックス i を取得します。
  • L1 から i 番目の要素を削除します。
  • ans に i を加算します。
• 最後に ans を返します。

このアルゴリズムのポイントは、「L2 の先頭から順に要素を揃えていくとき、その要素を正しい位置まで移動させるのに必要な隣接スワップの回数は、現在の L1 内でのその要素のインデックスに等しい」という性質を利用している点です。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
    def solve(self, L1, L2):
        ans = 0
        for req in L2:
            i = L1.index(req)
            L1.pop(i)
            ans += i
        return ans

ob = Solution()
L1 = [0, 1, 2, 3]
L2 = [2, 0, 1, 3]
print(ob.solve(L1, L2))

入力

[0, 1, 2, 3],[2, 0, 1, 3]

出力

2

計算量について

この実装では、index() による検索と pop() による削除がそれぞれ O(n) のコストを持つため、全体の計算量は O(n²) になります。リストのサイズが大きい場合は、Binary Indexed Tree（BIT）やマージソートを使って転倒数を求める手法を採用すると、O(n log n) まで高速化できます。