LeetCode / Roman to Integer

（ブログ記事からの転載）

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

その名の通り、ローマ数字を数値に変換するという問題です。
"IV"なら4、"VI"なら6と、ローマ数字中の文字のある場所によって数値が変わるのがポイントですね。

回答・解説

解法1

どの解法でもポイントになるのは、ローマ数字に対してループを回したとき、今の桁の数が次の桁の数よりも小さかったら、今の桁の数の分だけ値を引く点です。
つまり、"VI"のように"I"の前に"V"とより大きな値が来た時はそのまま5+1=6と足せば良いが、"IV"のように"V"の前に"I"とより小さな値が来た時は5-1=4と引く必要があります。
これをコードに反映します。

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}
        z = 0
        for i in range(0, len(s) - 1):
            if d[s[i]] < d[s[i+1]]:
                z -= d[s[i]]
            else:
                z += d[s[i]]
        return z + d[s[-1]]

d[s[i]] < d[s[i+1]]の場合はzからd[s[i]]を引くことで、上記ポイントを反映します。

最後の桁は次の桁との比較ができないので、ループの外でd[s[-1]]を足して、最終的な答えとします。

解法2

基本的な考えは解法1と同じですが、より短く・早くを志向します。
例えば以下のようなコードが考えられます。

class Solution:
    def romanToInt(self, s):
        d = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
        z, p = 0, 'I'
        for c in s[::-1]:
            z, p = z - d[c] if d[c] < d[p] else z + d[c], c
        return z

ループを回す際、変数pに前の桁の数が入るようにして、次の桁の数である変数cに対して、d[c]とd[p]を比較しています。

d[c] < d[p]の場合にzからd[c]を引くというのは解法1と全く同じロジックですね。