Roman to Integer

アルゴリズム概要

Python実装

from __future__ import annotations

from typing import Dict, Final, Optional


class Solution:
    """
    Roman to Integer (LeetCode 13) を解決するクラス。

    ローマ数字を表す文字列を受け取り、対応する整数値を返す。
    """

    # クラス変数として文字→数値の対応表を保持する。
    # インスタンスごとに作り直す必要がないデータなので、
    # __init__の中ではなくクラス変数として持たせることでメモリを節約できる。
    _ROMAN_VALUES: Final[Dict[str, int]] = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    }

    def romanToInt(self, s: str) -> int:
        """
        ローマ数字の文字列を整数に変換する。

        Args:
            s: 変換対象のローマ数字文字列（例: "MCMXCIV"）。

        Returns:
            変換後の整数値（例: 1994）。

        Raises:
            TypeError: 入力が文字列でない場合。
            ValueError: 入力が空、または未知の文字を含む場合。
        """
        # 入力検証（防御的プログラミング：制約上は保証されているが、
        # 誤った呼び出しをされても安全に動作するようにする）
        self._validate(s)

        # ループの外で対応表への参照をローカル変数に束縛しておく。
        # self._ROMAN_VALUES というアクセスはPythonの内部で属性検索を
        # 伴うため、ループの外で1回だけ済ませておくと検索コストを省ける。
        values = self._ROMAN_VALUES
        total = 0
        length = len(s)

        # 左から右へ1文字ずつ走査する
        for i in range(length):
            current = values[s[i]]

            # 次の文字が存在する場合のみその値を取得し、
            # 存在しない場合はNoneとして扱う。
            next_value: Optional[int] = values[s[i + 1]] if i + 1 < length else None

            # 現在値が次の値より小さい場合は「引き算ルール」
            # （IV, IX, XL, XC, CD, CM の6パターン）に該当する。
            if next_value is not None and current < next_value:
                total -= current
            else:
                total += current

        return total

    def _validate(self, data: object) -> None:
        """型安全な入力検証を行う"""
        if not isinstance(data, str):
            raise TypeError("Input must be a string")

        if len(data) == 0:
            raise ValueError("Input cannot be empty")

        # all() + ジェネレータ式で全文字の妥当性チェックを1行で行う。
        if not all(char in self._ROMAN_VALUES for char in data):
            raise ValueError("Input contains invalid roman numeral characters")

i=0: current='M'(1000), next='C'(100)  → 1000 < 100 は偽 → 加算 → total=1000
i=1: current='C'(100),  next='M'(1000) → 100 < 1000 は真  → 減算 → total=900
i=2: current='M'(1000), next='X'(10)   → 1000 < 10 は偽   → 加算 → total=1900
i=3: current='X'(10),   next='C'(100)  → 10 < 100 は真    → 減算 → total=1890
i=4: current='C'(100),  next='I'(1)    → 100 < 1 は偽     → 加算 → total=1990
i=5: current='I'(1),    next='V'(5)    → 1 < 5 は真       → 減算 → total=1989
i=6: current='V'(5),    next=なし      → 無条件で加算       → total=1994
出力: 1994 ✅

計算量分析

📖 用語集

このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください（五十音順）。