Pythonでスタックの要素がペアごとに連続しているかどうかを確認する方法

数値のスタックが与えられたとき、スタック内の値がペアごとに連続している（consecutive）かどうかを判定する問題を考えてみましょう。ここでいう「連続」とは、各ペアの2つの値の差がちょうど1であることを意味し、ペアは増加方向でも減少方向でも構いません。また、スタックの要素数が奇数の場合は、先頭（トップ）の要素はペアの対象外となります。さらに重要な点として、判定処理を行った後も元のスタックの内容を保持しておく必要があります。

この問題を解くには、スタックに対して push（プッシュ）、pop（ポップ）、空かどうかの確認 の3つの基本操作のみを使用します。

例えば、入力が stk = [5, 6, -4, -5, 12, 11, 6, 7, 22] の場合、出力は True になります。これは、トップの要素 22 を除外すると、残りのペアが [(5, 6), (-4, -5), (12, 11), (6, 7)] となり、すべてのペアが連続しているためです。

解法のアルゴリズム

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

• stk の要素をすべて pop して、一時スタック temp に push する
• 元のスタック stk をクリアする
• フラグ flag を True で初期化する
• temp のサイズが 1 より大きい間、以下を繰り返す
  • temp の上位2つの要素を取り出し（pop）、item_first と item_second とする
  • |item_first − item_second| が 1 でない場合は、flag を False にする
  • item_first と item_second を stk に push して戻す
• temp のサイズが 1 のまま残っている場合は、そのトップ要素を stk に push する
• flag を返す

実装例

以下のコードで具体的な実装を確認してみましょう。

def solve(stk):
    temp = stk[::-1]
    stk.clear()

    flag = True
    while len(temp) > 1:
        item_first = temp[-1]
        temp.pop()
        item_second = temp[-1]
        temp.pop()
        if abs(item_first - item_second) != 1:
            flag = False

        stk.append(item_first)
        stk.append(item_second)

    if len(temp) == 1:
        stk.append(temp[-1])

    return flag

stk = [5, 6, -4, -5, 12, 11, 6, 7, 22]
print(solve(stk))

入力

[5, 6, -4, -5, 12, 11, 6, 7, 22]

出力

True

コードのポイント

この実装では、まずスライス [::-1] を使ってスタックの要素を逆順にコピーし、一時リスト temp を作成しています。これにより、元の順序を保ったまま要素を2つずつ取り出せるようになります。各ペアの差の絶対値が1でなければ flag を False に更新し、最終的にその結果を返します。同時に、取り出した要素はすべて元のスタック stk に戻されるため、処理後もスタックの内容は元のまま維持されます。計算量は O(n)、必要な追加領域も O(n) であり、効率的な解法となっています。