Pythonで解く「野球ゲーム」スコア計算問題 ― スタックを使った実装方法

野球ゲームの得点記録プログラムを考えてみましょう。文字列のリストが与えられ、各文字列は次の4種類のいずれかであるとします。

• 整数(その回のスコア) ― この回で獲得する得点をそのまま表します。
• "+"(その回のスコア) ― 直前の2つの有効な回の得点の合計が、この回の得点になります。
• "D"(その回のスコア) ― 直前の有効な回の得点を2倍した値が、この回の得点になります。
• "C"(操作であり、スコアではない) ― 直前の有効な回の得点が無効であったことを意味し、その得点を記録から取り消します。

ここで重要なのは、各回の操作が永続的であり、前後の回の計算に影響を及ぼしうるという点です。最終的に、すべての回で獲得できる得点の合計を求める必要があります。

入力例と処理の流れ

たとえば、入力が ["5","2","C","D","+"] の場合、出力は 30 になります。処理は以下のように進みます。

• 1回目 ― 5点を獲得。合計: 5
• 2回目 ― 2点を獲得。合計: 7
• 操作1("C")― 2回目の得点が無効になり、取り消される。合計: 5
• 3回目("D")― 直前の有効な得点5を2倍し、10点を獲得。合計: 15
• 4回目("+")― 直前の2つの有効な得点 5 + 10 = 15点を獲得。合計: 30

解法のアプローチ

この問題はスタック(リスト)を使うことで効率的に解けます。手順は以下の通りです。

• 空のスタックを用意します。
• ops の各要素 i に対して、次の処理を行います。
  • i が "+" の場合: スタック末尾の2つの要素を取得し、その合計をスタックに追加します。
  • i が "D" の場合: スタック末尾の要素を2倍した値をスタックに追加します。
  • i が "C" の場合: スタック末尾の要素を削除(ポップ)します。
  • それ以外の場合: i を整数に変換してスタックに追加します。
• 最後に、スタック内の全要素の合計を返します。

スタックを使うことで、「直前の有効な得点」への参照や取り消し操作を O(1) で行えます。全体の計算量は要素数を n とすると時間 O(n)、空間 O(n) となります。

Pythonでの実装例

class Solution:
    def calPoints(self, ops):
        stack = []
        for i in ops:
            if i == "+":
                first, second = stack[len(stack) - 1], stack[len(stack) - 2]
                stack.append(first + second)
            elif i == "D":
                stack.append(stack[-1] * 2)
            elif i == "C":
                stack.pop()
            else:
                stack.append(int(i))
        return sum(stack)

ob = Solution()
print(ob.calPoints(["5","2","C","D","+"]))

入力

["5","2","C","D","+"]

出力

30

このように、スタックの「後入れ先出し(LIFO)」という性質を利用すれば、得点の追加・倍加・取り消しといった操作をシンプルかつ効率的に処理できます。類似の問題として、ブラウザの履歴管理やテキストエディタの「元に戻す(Undo)」機能なども同じ考え方で実装できるため、スタックの理解を深める良い練習題材といえるでしょう。