Pythonでブロックの高さリストが直線y=xに対して対称かどうかを判定するプログラム

数値のリスト nums があるとします。これは正方形のブロックを横一列に並べたときの、各列の高さを表しています。ここで、このブロック形状が直線 y = x に対して対称であるかどうかを判定する必要があります。

たとえば、入力が nums = [7, 5, 3, 2, 2, 1, 1] の場合、出力は True になります。

解き方のアプローチ

この問題は、リストの両端から同時に走査していくことで効率的に判定できます。手順は次のとおりです。

• i を 0、j を「リストの長さ - 1」で初期化します。
• i <= j である間、次の処理を繰り返します。
  • h := nums[j](右側の列の高さ)とします。
  • i < h である間、次の処理を繰り返します。
    • nums[i] が j + 1 と等しくない場合は False を返します。
    • i を 1 増やします。
  • j を 1 減らします。

すべての確認を通過できたら、True を返します。

なぜこれで対称性を判定できるのか

直線 y = x に対する対称とは、ブロック形状を45度の対角線で折り返したときに、元の形とぴったり重なる状態を指します。右端の列 j の高さ h が決まると、対角線で折り返した先の領域には、必ず高さが j + 1 となる列が並んでいなければなりません。この対応関係を右端から順に検証し、1箇所でも矛盾が見つかれば非対称(False)、最後まで矛盾がなければ対称(True)と判断できます。計算量は要素数を n として O(n) で済むため、非常に効率的です。

実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
   def solve(self, nums):
      i = 0
      j = len(nums) - 1
      while i <= j:
         h = nums[j]
         while i < h:
            if nums[i] != j + 1:
               return False
            i += 1
         j -= 1
      return True

ob = Solution()
nums = [7, 5, 3, 2, 2, 1, 1]
print(ob.solve(nums))

入力

[7, 5, 3, 2, 2, 1, 1]

出力

True