Pythonでリストの部分リストを反転させて別のリストと一致させられるか判定するプログラム

問題概要

2つの数値リスト A と B が与えられたとします。リスト A 内の任意の部分リスト(サブリスト)を選んで反転することができ、この操作は何度でも繰り返せます。このとき、A を B と同じ並びに変換できるかどうかを判定するのが目的です。

例えば、入力が A = [2, 3, 4, 9, 10]、B = [4, 3, 2, 10, 9] の場合、[2, 3, 4] と [9, 10] の2つの部分リストをそれぞれ反転するだけでよいので、出力は True になります。

解き方のポイント

実は、「部分リストの反転を何度でも行える」という条件があるため、隣接する2要素だけを反転することも可能です。これはつまり、任意の順列を作り出せることを意味します。したがって、A と B に含まれる各要素の出現回数(頻度)が完全に一致していれば、必ず A を B に変換できることになります。

そこで、次の手順で判定を行います。

• 結果を格納するマップ res を用意し、初期状態は空にします。
• nums の各要素 n について、res[n] に 1 を加算します。
• target の各要素 t について、res[t] から 1 を減算します。
• res のすべての値が 0 になっていれば true を返します。

実装例(Python)

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

from collections import defaultdict
class Solution:
    def solve(self, nums, target):
        res = defaultdict(int)
        for n in nums:
            res[n] += 1
        for t in target:
            res[t] -= 1
        return all(n == 0 for n in res.values())
ob = Solution()
A = [2, 3, 4, 9, 10]
B = [4, 3, 2, 10, 9]
print(ob.solve(A, B))

入力

[2, 3, 4, 9, 10], [4, 3, 2, 10, 9]

出力

True