# 12 - Integer to Roman

解法一 - 一次處理一個 digit

最直觀的做法就是直接寫下每一個 digit 碰到每一位要怎麽處理，不過也要注意處理到十 百 千這三位時，要把處理完的字串 insert 到答案的最前面：

class Solution {
public:
    string intToRoman(int num) {
        string res;

        for(int i=0; i<4; i++) {
            int digit = num%10;
            num /= 10;

            if(digit == 0) continue;

            if(i == 0) {
                if(digit <= 3) {
                    for(int j=0; j<digit; j++)
                        res += "I";
                }
                else if(digit == 4) res += "IV";
                else if(digit == 5) res += "V";
                else if(5< digit && digit <= 8) {
                    res += "V";
                    for(int j=0; j<digit-5; j++)
                        res += "I";
                }    
                else if(digit == 9) res += "IX";
            }
            else if(i == 1) {
                if(digit <= 3) {
                    for(int j=0; j<digit; j++)
                        res.insert(0, "X");
                }
                else if(digit == 4) res.insert(0, "XL");
                else if(digit == 5) res.insert(0, "L");
                else if(5< digit && digit <= 8) {
                    res.insert(0, "L");
                    for(int j=0; j<digit-5; j++)
                        res.insert(j+1, "X");
                }    
                else if(digit == 9) res.insert(0, "XC");
            }
            else if(i == 2) {
                if(digit <= 3) {
                    for(int j=0; j<digit; j++)
                        res.insert(0, "C");
                }
                else if(digit == 4) res.insert(0, "CD");
                else if(digit == 5) res.insert(0, "D");
                else if(5< digit && digit <= 8) {
                    res.insert(0, "D");
                    for(int j=0; j<digit-5; j++)
                        res.insert(j+1, "C");
                }    
                else if(digit == 9) res.insert(0, "CM");
            }
            else if(i == 3) {
                for(int j=0; j<digit; j++)
                    res.insert(0, "M");
            }
        }

        return res;
    }
};

這樣做的缺點是程式碼很複雜，也比較容易出錯。雖然效率還可以：

Runtime: 8 ms, faster than 78.84% of C++ online submissions for Integer to Roman. Memory Usage: 8.5 MB, less than 67.74% of C++ online submissions for Integer to Roman.

解法二 - 查表法

其實一開始腦海中也有閃過這個做法，不過心裡還是想試試看能不能用最簡單的邏輯寫看看，不過如果真的面試遇到，用查表法可能還是比較理想，因為錯誤率低不少：

class Solution {
public:
    string intToRoman(int num) {
        vector<string> M = {"", "M", "MM", "MMM"};
        vector<string> C = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        vector<string> X = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        vector<string> I = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
    }
};