🐧

#3:LeetCode Roman to Integer

に公開
Python
LeetCode
tech

問題(GPT翻訳)

与えられたローマ数字文字列 s を、その整数値に変換せよ。

ローマ数字の基本記号と値：I=1, V=5, X=10, L=50, C=100, D=500, M=1000

通常は左から右へ加算するが、小さい値が大きい値の左にあるときは減算する
（例：IV=4, IX=9, XL=40, XC=90, CD=400, CM=900）。

制約

1 <= s.length <= 15
s は 'I','V','X','L','C','D','M' のみを含む
問題の入力は常に有効なローマ数字（範囲 1〜3999）

解法

初めに思いついた解法

  • 方針
    • 前から順にルールの通り次の値を見て、減算か加算かを判断する
from typing import Final

ROMAN_TO_VALUE: Final[dict[str, int]] = {
    "M": 1000,
    "D": 500,
    "C": 100,
    "L": 50,
    "X": 10,
    "V": 5,
    "I": 1,
}


class Solution:
    def romanToInt(self, s: str) -> int:
        total = 0
        for i in range(len(s) - 1):
            if ROMAN_TO_VALUE[s[i]] < ROMAN_TO_VALUE[s[i + 1]]:
                total -= ROMAN_TO_VALUE[s[i]]
            else:
                total += ROMAN_TO_VALUE[s[i]]

        total += ROMAN_TO_VALUE[s[-1]]

        return total
  • 時間計算量・空間計算量
    • 時間計算量：入力分を走査しているだけであるため、O(n)
    • 空間計算量：ROMAN_TO_VALUE は固定サイズのマップ（定数）なので O(1)

最終的な解法

逆側から読んでいくことで、これまで必要だったforループ後の末尾加算が不要になりました。
足し忘れのようなロジック漏れも防げて、わかりやすくなりました。

from typing import Final

ROMAN_TO_VALUE: Final[dict[str, int]] = {
    "M": 1000,
    "D": 500,
    "C": 100,
    "L": 50,
    "X": 10,
    "V": 5,
    "I": 1,
}


class Solution:
    def romanToInt(self, s: str) -> int:
        total, prev = 0, 0
        for r in reversed(s):
            cur = ROMAN_TO_VALUE[r]
            if cur < prev:
                total -= cur
            else:
                total += cur
            prev = cur

        return total

別解

Pythonぽさを出すならitertools.pairwise(Python 3.10+)を使用する方法もあります。
同じような解法でzip(s, s[1:])を使った方法もありますが、今回のようにペアでzipしようと思うとs[1:]のスライスが新しい文字列を生成するため追加のO(n)メモリ／コピーが発生するので今回は採用しませんでした(時間計算量はどちらもO(n))。
itertools.pairwise(Python 3.10+)であれば、コピーを作らずペアを返してくれます。

from itertools import pairwise
from typing import Final

ROMAN_TO_VALUE: Final[dict[str, int]] = {
    "M": 1000,
    "D": 500,
    "C": 100,
    "L": 50,
    "X": 10,
    "V": 5,
    "I": 1,
}

class Solution:
    def romanToInt(self, s: str) -> int:
        total = 0
        # pairwise は隣接要素のタプルを逐次返す
        for cur, nxt in pairwise(s):
            if ROMAN_TO_VALUE[cur] < ROMAN_TO_VALUE[nxt]:
                total -= ROMAN_TO_VALUE[cur]
            else:
                total += ROMAN_TO_VALUE[cur]

        total += ROMAN_TO_VALUE[s[-1]]

        return total

テストケース

s = Solution()
test_cases = [
    (1, "I", 1),
    (2, "III", 3),
    (3, "IV", 4),
    (4, "IX", 9),
    (5, "LVIII", 58),
    (6, "XC", 90),
    (7, "CD", 400),
    (8, "CM", 900),
    (9, "MCMXCIV", 1994),
    (10, "MMMCMXCIX", 3999)
]

for no, roman, expected in test_cases:
    got = s.romanToInt(roman)
    assert got == expected, f"Test No{no} failed for '{roman}'. expected {expected}, got {got}"

学び・気づき

  • ローマ数字を初めて理解した
  • 逆順にすれば終端処理をしなくて済むことがわかったし、計算量にも大きな影響ではない
  • itertoolsは便利なものがいっぱいあるので、使い方を学びアウトプットしてみる

参考

GitHubで編集を提案

Discussion