LeetCode Problems解いた：13. Roman to Integer

LeetCodeの問題集、13. Roman to Integerがacceptされたので、備忘録として。

概要

ローマ数字をアラビア数字の整数に変換する、というアルゴリズムを作成する問題。

コード

今回はC#での記述。

Solution.cs

public class Solution {
    public int RomanToInt(string s) {
        // 初期設定
        int num = 0;
        string tmpstr = s; //区切られる文字列の入れ物
        int arraySize;
        //文字と数字の対応表(処理の都合で降順に並べている)
        Dictionary<string, int> romanDict = new Dictionary<string, int> {{"M",1000},{"D",500},{"C",100},{"L",50},{"X",10},{"V",5},{"I",1}};
        //処理部；大きい数字から処理
        foreach(KeyValuePair<string, int> dictItem in romanDict){
            //foreachで取り出された要素のキーで文字列を分割
            string[] tmparr = tmpstr.Split(dictItem.Key);
            arraySize = tmparr.Length;
            //キーが示す整数で加算する処理
            for(int i = 0; i < arraySize - 1; i++){
                if (tmparr[i] == ""){
                    num = num + dictItem.Value; //空文字なら加算
                }else{
                    num = num + dictItem.Value - romanDict[tmparr[i]]; //文字が入ってるなら引いてから加算
                }
            }
            //残った右端をtmpstrに入れ替えて、次のループへ持っていく。
            tmpstr = tmparr[arraySize - 1];
        }
        return num;
    }
}

考え方

まず20ぐらいまでのローマ数字しか見たことがなかったので、どう読むのか、というところからスタート。
結局どんな仕組みだったかというと、

• 左から大きい順に並んでいる
• 左から順に足す
• 4、9を表す際は左に引く数字がつく。(4：IV→5−1、9：IX→10−1　etc.)

という感じ。なので、ローマ数字を左から、大きい数字を表すアルファベット順に見ていって足す、という処理をしたい。

1. 「大きい数字を表すアルファベット順に見ていって」をするため、順番に並べた辞書を準備。(l.8)

2. 「大きな数字を表すアルファベット順に見る」ため、foreachで1.の辞書内を巡回。(l.10)

3. 文字列tmpstrを分割、加算処理(l.12−21)
   例)"MCMXCIV"=1994 を"M"で分割
   →["","C","XCIV"]という配列になる。この時、""="M"=1000、"C"="CM"=900となる。
   つまり、区切った後の配列の要素を見て、要素が空文字であれば区切った文字が表す整数を加算、空文字でなければ[区切った文字]-[入っている文字]を加算すればよい。
   そして、一番右(配列の一番最後；"XCIV")は、必然的にMより小さい文字の集まりになるので、今度はそれをtmpstrとし、次に大きな整数を表す文字で分割する。以下繰り返し。

"MCMXCIV"=1994の詳細フロー

Loop1: tmpstr="MCMXCIV" → Mで分割 → ["","C","XCIV"] → num=1900、tmpstr="XCIV"

Loop2: tmpstr="XCIV" → Dで分割 → ["XCIV"] → num=1900+0、tmpstr="XCIV"

Loop3: tmpstr="XCIV" → Cで分割 → ["X","IV"] → num=1900+90、tmpstr="IV"

Loop4、５: tmpstr="IV" → L,Xで分割 → ["IV"] → num=1990+0、tmpstr="IV"

Loop6: tmpstr="IV" → Vで分割 → ["I"] → num=1990+4、tmpstr="I"

Loop7: tmpstr="I" → Iで分割 → exit → return　num(=1994)

自分の結果

計算速度：上から数えて約90%のところ(超下の方)
メモリ使用量：上から数えて50%強のところ(真ん中ぐらい)
あまり早く動作するアルゴリズムにはならず。

備考