Roman to Integer
ローマ数字では7つの記号を使用します。I = 1、V = 5、X = 10、L = 50、C = 100、D = 500、M = 1000です。記号は大きいものから小さいものへと並べて足し合わせます。ただし、引き算を表す6つの組み合わせでは、小さい記号が先に置かれ、大きい記号から差し引かれます。IV = 4、IX = 9、XL = 40、XC = 90、CD = 400、CM = 900です。
有効なローマ数字sが与えられます。それが表す整数を返してください。
関数
- sstring
- 大文字の有効なローマ数字
- 戻り値integer
- 数値の値（1～3999）
制約
1 ≤ s.length ≤ 15sに含まれるのは、文字I、V、X、L、C、D、Mのみです。sは、1から3999までの値を表す有効なローマ数字です。
例
- 入力
- s = "XXVII"
- 出力
- 27
- 説明
XXは10 + 10、Vは5、IIは1 + 1を表すので、合計は27です。どの記号の後にもそれより大きい記号は続かないため、すべての記号を加算します。
- 入力
- s = "CDXLIV"
- 出力
- 444
- 説明
- この数は減算表記のペアが3つ連続しています。
CDは400、XLは40、IVは4なので、444になります。
- 入力
- s = "MCDXCII"
- 出力
- 1492
- 説明
Mは1000、CDは400、XCは90、IIは2なので、この数字は1492です。ペアと単独の記号は自由に組み合わせられます。
提出時に隠しテスト+22件
発展問題
1から3999までの整数をローマ数字に変換する、逆の処理を書けますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数字を記号ごとに1つずつの値として書き出します。
MCDXCIIは1000、100、500、10、100、1、1になります。合計が1492になるようにするには、これらの値のうちどれを負の値として数えればよいでしょうか？ある記号の直後にある記号の値がより大きい場合に限り、その記号は減算されます。
CDの C やXCの X がその例です。それ以外の記号はすべて加算されます。同じ値の記号が後に続く場合も同様で、IIがその例です。インデックスを使って文字列を一度走査します。現在の記号の値と次の記号の値を比較し、現在の記号の値が小さければ減算し、そうでなければ加算します。最後の記号には隣の記号がないため、常に加算します。
解説
数字表記の大部分は単純な加算なので、問題は6つの減算ペアを見つけることです。2文字のトークンとして調べることも、6つすべてに当てはまる次のルールを使うこともできます。右隣の記号より値が小さい記号は減算します。どちらの方法でも、最大15文字を1回走査すれば答えが得られます。
減算ペアをトークンとして読み取る
考え方
数字をトークンの並びとして考えましょう。ほとんどのトークンは1文字で、2文字のものは6つあります：IV、IX、XL、XC、CD、CM。文字列をこれらのトークンに分割し、それぞれの値を合計すれば、数値が得られます。
各位置で、まず次の2文字を確認します。それが6つのペアのいずれかなら、そのペアの値を加えて、2文字分進みます。そうでなければ、1文字の値を加えて、1文字分進みます。MCDXCIIはM、CD、XC、I、Iに分割されます：1000 + 400 + 90 + 1 + 1 = 1492。
ペアの確認は最初に行う必要があります。XCのXを単独で読み取ると、10を加えた後に100を加えることになり、90ではなく110になります。この確認は安全でもあります。有効な数字では、小さい記号の直後に大きい記号が来るのは、これら6つのペアのいずれかの場合だけなので、見つかったペアはすべて正しいものです。
各ステップで1文字または2文字を処理するため、ループは最大15回実行されます。2つのテーブルは固定サイズなので、追加の空間計算量は定数です。
アルゴリズム
- 6つのペア用に1つの表を作り、7つの単独の記号用にもう1つの表を作ります。
- 合計を0にして、インデックス0から始めます。
- インデックス位置の2文字がペアを形成している場合は、ペアの値を加算し、インデックスを2進めます。
- そうでない場合は、単独の記号の値を加算し、インデックスを1進めます。
- インデックスが末尾を過ぎたら、合計を返します。
def romanToInt(s):
pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
i = 0
while i < len(s):
two = s[i:i + 2]
if two in pairs:
total += pairs[two]
i += 2
else:
total += singles[s[i]]
i += 1
return total各記号を次の記号と比較する
考え方
6つのペアをもう一度見てみましょう。どのペアでも、最初の記号の値は2番目の記号より小さく、ペアの値は2番目から最初を引いたものです。そこで、ペアの表をなくして、1つのルールを使えます。記号の値が右隣の記号より小さい場合は引き、それ以外は足します。CMは-100 + 1000となり、トークンを読み取る方法と同じ値の900になります。
MCDXCIIを順に見ていきましょう。Mの後にはより小さいCが続くので、1000を足します。Cの後にはより大きいDが続くので、100を引きます。合計は900です。Dを足して1400になります。Xの後にはより大きいCが続くので、10を引き、1390になります。Cを足して1490になります。最初のIの後には同じIが続くので、それを足して1491になります。最後のIには隣の記号がないので、それも足して1492になります。
比較条件は厳密に「より小さい」でなければなりません。隣り合う記号が等しい場合は常に足します。これによってIIは2、XXは20になります。このルールが正しいのは、トークンを読み取る方法が正しいのと同じ理由です。有効な数字では、小さい記号が大きい記号の直前に来るのは、減算ペアの前半としての場合だけです。
各文字を1回ずつ確認し、合計を1つだけ保持するため、時間計算量はO(n)、追加の空間計算量はO(1)です。この方法で必要なのは、7つの記号の値と、各文字につき1回の比較だけです。
アルゴリズム
- 7つの記号それぞれの値を保存します。
- 0から始まる累計値を使って、
sのインデックスをループ処理します。 - 次の記号が存在し、現在の記号より値が大きい場合は、現在の値を引きます。
- そうでない場合は、現在の値を加えます。
- ループの後に累計値を返します。
def romanToInt(s):
values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
for i in range(len(s)):
value = values[s[i]]
# A symbol worth less than the one after it is subtracted, like the I in IV.
if i + 1 < len(s) and value < values[s[i + 1]]:
total -= value
else:
total += value
return total
落とし穴と境界ケース
規則は短いため、間違いはその境界部分で起こります。
- 厳密に小さい場合ではなく、以下を使うこと。すると、最初の記号がそれぞれ引かれるため、
IIは 0、XXも 0 になります。 - 最後の文字で次の記号を読み取ること。そこには
s[i+1]は存在しません。まずi+1が長さの範囲内か確認し、最後の記号は必ず加算してください。 - トークン方式で、ペアより先に単独の記号を試すこと。すると
XCは 10 + 100 = 110 として読み取られます。 - ペアを2番目の記号でしか見つけないこと。
IVの I をすでに加算している場合は、1 + 5 - 2 × 1= 4 のように、2回差し引く必要があります。次の記号と比較すれば、この修正を避けられます。 - Lua と R の文字列はインデックスが 1 から始まることを忘れること。したがって、最後の記号は
#sまたはnchar(s)の位置にあります。
よくある質問4
Roman to Integer の時間計算量はどれくらいですか？
どちらのアプローチも各文字を1回ずつ読み取るため、n文字の数値に対する時間計算量はO(n)です。追加の空間計算量はO(1)です。これは、ルックアップテーブルのサイズが固定されているためです。1から3999までの数値は最大15文字なので、実際の処理量はごくわずかです。
なぜ、次の記号より小さい記号を引くのですか？
これが6つの減算ペアの仕組みです。IV、IX、XL、XC、CD、CMでは、小さい記号が大きい記号の前に置かれ、そのペアの値は大きい記号から小さい記号を引いた値になります。最初の記号を引いて2番目の記号を加えると、ちょうどその値になり、有効な数字の中で小さい記号が大きい記号の前に置かれる箇所はほかにありません。
ローマ数字を右から左へ変換できますか？
はい。最後の記号から最初の記号へと進み、前に読んだ記号、つまり右側にある記号の値を覚えておきます。現在の記号の値がその記号より小さければ引き算し、そうでなければ足し算します。反対側から見た、左から右へ進む場合と同じルールです。
この解決策は、その数値が有効かどうかを確認しますか？
いいえ。この問題では有効な数字が与えられると保証されているため、コードは加算と減算のみを行います。IIIIやVVのような無効な文字列が与えられても、4や10という数値を返します。検証するには、結果を数字に戻して入力と比較します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def romanToInt(s):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "XXVII"
期待値
27