【LeetCode】13. Roman to Integer解答・解説【Python】

LeetCodeの問題を解きます。問題文は翻訳サイトと私の拙い英語力で和訳しており、正確でない可能性が高いためご注意ください。

問題文
1. 原文
2. 和訳
方針
解答
1. コメント＋コード
  1. 別解
2. コードのみ
  1. 別解
補足・参考・感想

問題文

原文

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

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.

X can be placed before L (50) and C (100) to make 40 and 90.

C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Constraints:

1 <= s.length <= 15

s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').

It is guaranteed that s is a valid roman numeral in the range [1, 3999].

和訳

ローマ数字は7個の異なる記号で表されます。：I,V,X,L,C,D,M

記号と値の関係は以下の通り。

I： 1

V： 5

X： 10

L： 50

C： 100

D： 500

M： 1000

例えば、2はローマ数字ではⅡと書き、2つのⅠを組み合わせるだけです。12はⅫと書き、単純にⅩとⅡです。27はXXVⅡⅡと書き、XXとVとⅡを組み合わせています。

通常、ローマ数字は左から右に向かって大きい数から順に書きます。しかし、4はIIIIではありません。代わりにIVと書きます。1は5の前(左側)にあるので、5から1を引き算して4を作ります。同じ原理は9にも当てはまり、IXと書きます。引き算が使われる例は6つあります。

・IはVとXの前(左側)に置かれ、4と9を作ります。

・XはLとCの前(左側)に置かれ、40と90を作ります。

・CはDとMの前(左側)に置かれ、400と900を作ります。

ローマ数字が与えられるので、(アラビア)数字に変換してください。

制約

・与えられる文字列sの要素数は1~15

・sは('I', 'V', 'X', 'L', 'C', 'D', 'M')だけを含む

・sは!~3999までのローマ数字のみ

方針

・ローマ数字をアラビア数字に変化した後で、後ろ(右側)から足していきます。

・1つ前に足した数字を一時的な変数に保存し、次の数字が1つ前に足した数字よりも小さければ引き算します。

解答

コメント＋コード

#クラスを定義
class Solution:
　　#関数を定義。sはstr、返り値はint
    def romanToInt(self, s: str) -> int:
　　　　#合計値sum、1つ前に足した数字を保存する変数tmp、ローマ数字とアラビア数字を対応付けたdictを用意
        sum = 0
        tmp = 0
        roman_to_int_dict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
　　　　　#sを逆順に並べ替えてfor文で繰り返す
        for i in s[::-1]:
　　　　　　#iにアラビア数字に変換した数字を代入
            i = roman_to_int_dict[i]
　　　　　　#tmpがiよりも大きい、つまり1つ前に足した数字がiよりも大きい場合
            if tmp > i:
　　　　　　　　　#合計値からiを引く(例：IVなら5-1)
                sum -= i
　　　　　　　#tmpがi以下の場合
            else:
　　　　　　　　#合計値にiを加える
               sum += i
　　　　　　#tmpにiを代入する
            tmp = i
            
        return sum

#クラスを定義

class Solution:

　　#関数を定義。sはstr、返り値はint

def romanToInt(self, s: str) -> int:

　　　　#合計値sum、1つ前に足した数字を保存する変数tmp、ローマ数字とアラビア数字を対応付けたdictを用意

sum = 0

tmp = 0

roman_to_int_dict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}

　　　　　#sを逆順に並べ替えてfor文で繰り返す

for i in s[::-1]:

　　　　　　#iにアラビア数字に変換した数字を代入

i = roman_to_int_dict[i]

　　　　　　#tmpがiよりも大きい、つまり1つ前に足した数字がiよりも大きい場合

if tmp > i:

　　　　　　　　　#合計値からiを引く(例：IVなら5-1)

sum -= i

　　　　　　　#tmpがi以下の場合

else:

　　　　　　　　#合計値にiを加える

sum += i

　　　　　　#tmpにiを代入する

tmp = i

return sum

別解

class Solution:
    def romanToInt(self, s: str) -> int:
        sum = 0
        tmp = 0
        count = 0
        roman_to_int_dict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
　　　　　#for文でsの要素の数だけ繰り返す
        for i in range(len(s)):
　　　　　　　#繰り返した数だけ1を引く。s[count]とすることで後ろから要素を取り出せる
            count -= 1
　　　　　　　#アラビア数字に変換したローマ数字をiに代入。
            i = roman_to_int_dict[s[count]]
            
            if tmp > i:
                sum -= i
            else:
                sum += i
            tmp = i
            
        return sum

class Solution:

def romanToInt(self, s: str) -> int:

sum = 0

tmp = 0

count = 0

roman_to_int_dict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}

　　　　　#for文でsの要素の数だけ繰り返す

for i in range(len(s)):

　　　　　　　#繰り返した数だけ1を引く。s[count]とすることで後ろから要素を取り出せる

count -= 1

　　　　　　　#アラビア数字に変換したローマ数字をiに代入。

i = roman_to_int_dict[s[count]]

if tmp > i:

sum -= i

else:

sum += i

tmp = i

return sum

こちらの方法だと、1つめの解答よりも早くなりました。

コードのみ

class Solution:
    def romanToInt(self, s: str) -> int:
        sum = 0
        tmp = 0
        roman_to_int_dict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
        for i in s[::-1]:
            i = roman_to_int_dict[i]
            if tmp > i:
                sum -= i
            else:
                sum += i
            tmp = i
            
        return sum
            
        """
        IV,IX,XL,XC,CD,CM
        """

class Solution:

def romanToInt(self, s: str) -> int:

sum = 0

tmp = 0

roman_to_int_dict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}

for i in s[::-1]:

i = roman_to_int_dict[i]

if tmp > i:

sum -= i

else:

sum += i

tmp = i

return sum

"""

IV,IX,XL,XC,CD,CM

"""

別解

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

class Solution:

def romanToInt(self, s: str) -> int:

sum = 0

tmp = 0

count = 0

roman_to_int_dict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}

for i in range(len(s)):

count -= 1

i = roman_to_int_dict[s[count]]

if tmp > i:

sum -= i

else:

sum += i

tmp = i

return sum

補足・参考・感想

聞いたことがあるものや知っていることでも、英語になると途端に何を指しているのかわからなくなるなと思うことがあります。今回のRoman numeralもそうでした。

LeetCodeに取り組むような人が目指す職場は、英語でのコミュニケーションもあるでしょうし、英語のドキュメントを読むことも多そうです。それぞれの専門分野に限って使われる言葉もあるでしょうし、単純にコードを書くだけでなく、エンジニアが自然と触れているものに自分もどんどん触れていきたいと思います。

LeetCodeでは、自分の提出物が他の提出者と比べて早いか、メモリをどれだけ消費したかが示されます。単に正解するだけでなく、より良い書き方がないかを考えたり調べたりするうえでとてもモチベーションになります。できれば、読みやすさや理解のしやすさも忘れずに実装できるようになりたいです。

次の記事：14. Longest Common Prefix

記事一覧：LeetCode記事一覧