#はじめに
こんばんは.
M1就活生がLeetCodeから,easy問題を中心にPythonを用いて解いていきます.
↓では,解いた問題のまとめを随時更新しています.
まとめ記事
#問題
今回解いたのは,難易度easyから 問題13のRoman to Integer です.
問題としては,文字列s
で与えられるローマ数字を整数に直して値を出力するというもの.
ローマ数字は7種類の記号で表されており,それぞれ次の値となっています.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
入力例と出力例は以下の通りです.
Example 1:
Input: s = "III"
Output: 3
Example 2:
Input: s = "IV"
Output: 4
Example 3:
Input: s = "IX"
Output: 9
Example 4:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
このとき,4を表す数字はIIII
ではなくIV
,9はIX
となっています.
#書いたコード
とりあえず,思いついたままに書いてみました.
class Solution:
def romanToInt(self, s: str) -> int:
dic = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
reverse_s = s[::-1]
total, prev = 0, 0
for i in reverse_s:
if dic[i] >= prev:
total += dic[i]
else:
total -= dic[i]
prev = dic[i]
return total
まず,それぞれローマ数字とその値に対応する辞書を用意します.ローマ数字は通常,左から順に大きい数字となるように書くルールがあるそうです(知らなかった).そのためまずは,ローマ数字を反転させて,末尾から順に加算していきます.このとき,4はIV
,9はIX
などのルールがあるため,前の値と比較してそれ以上であれば現在の値を加算,そうでなければ減算することで引き算のルールに適用させました.
議論ページを見てみると,なるほどなと思うコードがありました.
class Solution:
def romanToInt(self, s: str) -> int:
translations = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
number = 0
s = s.replace("IV", "IIII").replace("IX", "VIIII")
s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
for char in s:
number += translations[char]
return number
ローマ数字の引き算を行うルールは全部で6通りらしいです.そのため,このコードのようにそれぞれのローマ数字を減算を使わない形に置換することで簡単に計算ができるみたいです(これはいい...).
#おわりに
Discussページでは,様々な言語での解き方を参照できるのでとてもおもしろいです.多角的な思考で問題を解けるようにこれからも頑張っていきたいですね.
今回書いたコードはGitHubにもあげておきます.