ローマ数字を整数に

IV を素直に足すと 6 になる

ローマ数字は I が 1、V が 5、X が 10、L が 50、C が 100、D が 500、M が 1000 です。左から順に足していけば III は 3、LVIII は 58 と正しく出ます。

ところが IV に同じやり方を使うと 6 になります。正解は 4 です。小さい記号が大きい記号の前に置かれたときだけ、足すのではなく引く。この例外をどう扱うかが、この問題のすべてです。

6 通りの分岐を書き出す前に

引き算になる並びは IV IX XL XC CD CM の 6 つしかありません。ですから「この 6 つを見つけたら特別扱いする」という方針でも解けます。ただしこの道を選ぶと、2 文字ぶんまとめて進める処理と 1 文字ずつ進める処理が混ざり、進める幅の管理でつまずきます。

その前に、6 つの並びに共通している性質を確かめてください。I は V より小さく、X は L より小さい。逆に VI や XI のような通常の並びでは、前の記号のほうが大きいか同じです。つまり記号の名前を 6 通り覚えなくても、隣り合う 2 つの値を比べるだけで、引くのか足すのかが決まります。

例外を列挙する前に、1 つのルールに畳めないかを疑う。この見方はほかの問題でも効きます。

畳めたルールをどう反映させるかは、もう一段の判断です。IV を「4 を足す」と読むこともできますし、「I を引いてから V を足す」と読むこともできます。前者は 2 文字まとめて進める必要があり、後者は 1 文字ずつのままで済みます。1 文字ずつ進む形に統一できれば、進める幅を数える処理そのものが消えます。

ちなみに MCMXCIV は 1994 です。M で 1000、次の C は後ろの M より小さいので引く側、その M は足す側、と順に見ていくと合計が合います。手で 1 回追ってみると、実装の形が見えてきます。

最後の 1 文字には、隣がいない

隣を見る書き方は、必ず末尾で壊れます。LVIII の最後の I を処理するとき、その次の文字は存在しません。

範囲の確認を and の左側に置いておくと、右側は安全に評価されます。末尾の要素は条件が成立しないので、自動的に「いつもどおりの扱い」へ落ちます。ローマ数字でも、末尾は必ず足す側になります。

やってみよう

romanToInt(s) を実装してください。s は 1 から 3999 までを表す正しいローマ数字の文字列です（不正な入力は来ません）。文字列を 1 回なめるだけの O(n) で、対応する整数を返してください。

1. 関数 romanToInt(s) を実装し、整数 (1〜3999) を返す
2. 減算表記 (IV, IX, XL, XC, CD, CM) を正しく扱う
3. O(n) で実装する (1 パス)