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

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

問題文
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つめの解答よりも早くなりました。

解答3：Python,英語コメント付き

#Calculate the sum of inputs which are converted from Roman to integer.
#By processing the input Roman numeral string in reverse order,the correct conversion is performed.

class Solution:
    def romanToInt(self, s: str) -> int:
        #Assign the value 0 to the variable sum_ and tmp
        sum_ = 0
        tmp = 0
        #Initilize hash table named "roman_to_int_dict".
        roman_to_int_dict = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}

        ##Start a loop to iterate over each element of "s" in reverse.
        for i in s[::-1]:
            #Update the value of "i" as the value of i-th element of hash table
            i = roman_to_int_dict[i]
            print(i,"i")
            #Check if the value of "tmp" is greater than i
            if tmp > i:
                #Decremenet "i" by the value of i.
                sum_ -= i
                print(sum_,"sum_","★")
            #If tmp is equal to i or less than i
            else:
                #increment the value of sum_ by i.
                sum_ += i
                print(sum_,"sum_","★★")
            #Update the value of tmp as i.
            tmp = i
            print(tmp, "tmp")
            print("-----")
        #Return sum_ 
        print(sum_,"sum_")
        return sum_か

#Calculate the sum of inputs which are converted from Roman to integer.

#By processing the input Roman numeral string in reverse order,the correct conversion is performed.

class Solution:

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

#Assign the value 0 to the variable sum_ and tmp

sum_ = 0

tmp = 0

#Initilize hash table named "roman_to_int_dict".

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

##Start a loop to iterate over each element of "s" in reverse.

for i in s[::-1]:

#Update the value of "i" as the value of i-th element of hash table

i = roman_to_int_dict[i]

print(i,"i")

#Check if the value of "tmp" is greater than i

if tmp > i:

#Decremenet "i" by the value of i.

sum_ -= i

print(sum_,"sum_","★")

#If tmp is equal to i or less than i

else:

#increment the value of sum_ by i.

sum_ += i

print(sum_,"sum_","★★")

#Update the value of tmp as i.

tmp = i

print(tmp, "tmp")

print("-----")

#Return sum_

print(sum_,"sum_")

return sum_か

2周目に突入しました。

解答の内容は1つ目と同じです。

英語面接に向けてまずはコメントを英語で記載できるようにしていきます。

自力で解答できるようになることは絶対ですが、解答の過程を英語で考えて説明できるようになることも必須です。

あと何周するとこれを満たせるのかわかりませんが、1つずつ積み上げていきたいと思います。

時間計算量は入力文字列sを一巡して走査するのでO(n)。

空間計算量は連想配列を使っているのでこれもO(n)でしょうか。

計算量の考え方はいまだに慣れません。正解しているかもよくわからないのですが、ちょくちょく調べながら考えていきたいと思います。

解答4:Python, 英語コメント

"""
Before start coding, let me talk to you about a few things.
About question, assumption, testcases, approach


■Question
So first, let me check about my understand of your question.

I'm given nums and simbols.
nums has integer valuables.
And simbols are represent Roman numerals.
I have to return Roman numerals converted from the value of nums.

Is it correct?
OK. let's step to the next.

■Assumption
I wanna clarify some things.
 -Is the range of the value of nums 1 to 10^4(ten to power of 4)?
 -

■Testcases
 1.general cases
  -1
   →I
  -4
   →IV
  -1945
   →MCMXLV
 2.edge cases
  -
  -

■Approach
 1.Brure Force?
    Initilize hashmap. Its keys are number, and its values are Roman numerals.
    And perform for loop iteration to hasmap's keys in descending order.
    In each iterate, performe inner loop while nums is bigger than loop variables.
    In each inner iterate, Roman numeral is added to the variables whici is going to be returned.
    And nums is decremented by current loop variables.
    After loop, return the variables which has Roman numerals.


"""


class Solution:
    def intToRoman(self, num: int) -> str:
        dict1 = {
            "M":1000,
            "CM":900,
            "D":500,
            "CD":400,
            "C":100,
            "XC":90,
            "L":50,
            "XL":40,
            "X":10,
            "IX":9,
            "V":5,
            "IV":4,
            "I":1,
        }
        dict2 ={
            1000:"M",
            900:"CM",
            500:"D",
            400:"CD",
            100:"C",
            90:"XC",
            50:"L",
            40:"XL",
            10:"X",
            9:"IX",
            5:"V",
            4:"IV",
            1:"I",
        } 

        answer = ""
        for i in dict2.keys():
            while num >= i:
                answer += dict2[i]
                num -= i
        return answer

"""

Before start coding, let me talk to you about a few things.

About question, assumption, testcases, approach

■Question

So first, let me check about my understand of your question.

I'm given nums and simbols.

nums has integer valuables.

And simbols are represent Roman numerals.

I have to return Roman numerals converted from the value of nums.

Is it correct?

OK. let's step to the next.

■Assumption

I wanna clarify some things.

-Is the range of the value of nums 1 to 10^4(ten to power of 4)?

■Testcases

1.general cases

-1

→I

-4

→IV

-1945

→MCMXLV

2.edge cases

■Approach

1.Brure Force?

Initilize hashmap. Its keys are number, and its values are Roman numerals.

And perform for loop iteration to hasmap's keys in descending order.

In each iterate, performe inner loop while nums is bigger than loop variables.

In each inner iterate, Roman numeral is added to the variables whici is going to be returned.

And nums is decremented by current loop variables.

After loop, return the variables which has Roman numerals.

"""

class Solution:

def intToRoman(self, num: int) -> str:

dict1 = {

"M":1000,

"CM":900,

"D":500,

"CD":400,

"C":100,

"XC":90,

"L":50,

"XL":40,

"X":10,

"IX":9,

"V":5,

"IV":4,

"I":1,

}

dict2 ={

1000:"M",

900:"CM",

500:"D",

400:"CD",

100:"C",

90:"XC",

50:"L",

40:"XL",

10:"X",

9:"IX",

5:"V",

4:"IV",

1:"I",

}

answer = ""

for i in dict2.keys():

while num >= i:

answer += dict2[i]

num -= i

return answer

実際の面接の流れを意識して最初に英語で確認すべき内容を記載。

これをより内容を改善したうえで、緊張している中で口頭で説明できるようになる必要がある。

補足・参考・感想

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

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

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

次の記事：14. Longest Common Prefix

記事一覧：LeetCode記事一覧