LeetCode解説　一日一問　13.Roman to Integer

LeetCodeって？
問題
回答
コード
結果

LeetCodeって？

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

問題

Roman to Integer - LeetCode

Can you solve this real interview question? Roman to Integer - Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol ...

タイトル：13.Roman to Integer

難易度：Easy

内容：

ローマ数字で書かれた数値を整数に変換する。

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

例：

Input: s = "III"
Output: 3

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

基本的には出現する文字に対応する数値を足していけばいいのですが、 4 や 9 などは特殊なので別途対応が必要になります。

回答

基本的には出現したローマ数字に該当する数値を足していくことで実現できます。

例えば、

s = "LVIII"

の場合、L:50 + V:5 + I:1 + I:1 + I:1 = 58です。

しかし、IV = 4、IX = 9、XL = 40など、単位が変わる直前では手前についたローマ数字がマイナスの意味を持ちます。（IV ➡ -1 + 5 = 4、XL ➡ -10 + 50 = 40）

なので次のように考えます。

“MCMXCIV”（1994）の場合を考えます。

ローマ数字： "MCMXCIV"
数値 :  1994

ローマ数字を反転させます。

"VICXMCM"

反転させたので基本小さい数値のものから並んでいるはずです。

しかし、V：5の次にI：1が来ています。左の数値より小さいものが来たということは引く必要があるということです。なのでVIは 5 – 1 = 4 となります。

同じようにしていくと、
5 – 1 + 100 – 10 + 1000 – 100 + 1000 = 1994
となります。

コード

上記の理論を実装します。

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_dict = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000} # ローマ数字辞書
        ans = 0 # 返り値初期化
        left= -1 # 左隣の数値
        for i in range(len(s)):
            tmp_value = roman_dict[s[- i - 1]] # s に格納された文字の後ろから見ていき整数に変換
            if tmp_value < left: # これまでに登場した最大のローマ数字より大きければ
                tmp_value = -tmp_value # 符号反転
            left = tmp_value 
            ans += tmp_value
        return ans

計算量はO(N)です。

コードはgithubにも保管しています。