12. Число записать в римской нотации (Integer to Roman)

Задание.

Дано число.

Нужно сформировать для него строку в римской нотации.

Римские цифры представлены семью различными символами: I, V, X, L, C, D и M.

Например, 2 записывается как II римской цифрой, просто две единицы складываются вместе. 12 записывается как XII, что означает просто X + II. Число 27 записывается как XXVII, то есть XX + V + II.

Римские цифры обычно пишутся от наибольшего к наименьшему слева направо. Однако цифра, обозначающая четыре, не является IIII. Вместо этого число четыре записывается как IV. Поскольку единица стоит перед пятеркой, мы вычитаем ее, получая четыре. Тот же принцип применим к числу девять, которое записывается как IX. Существует шесть случаев, когда используется вычитание:

• I можно поместить перед V (5) и X (10), чтобы получилось 4 и 9.

• X можно поместить перед L (50) и C (100), чтобы получилось 40 и 90.

• C можно поместить перед D (500) и M (1000), чтобы получилось 400 и 900.

Пример 1.

Входные данные: num = 3

Результат: “III”

Пояснение: 3 = III.

Пример 2.

Входные данные: num = 58

Результат: “LVIII”

Пояснение: L = 50, V= 5, III = 3.

Пример 3.

Входные данные: num = 1994

Результат: “MCMXCIV”

Пояснение: M = 1000, CM = 900, XC = 90 и IV = 4.

Решение.

class Solution {
public:
    string intToRoman(int num) {
        string ss = "";
        vector<pair<int,string>> v = {
            {1000,"M"}, {900,"CM"}, {500,"D"}, {400,"CD"}
            , {100,"C"}, {90,"XC"}, {50,"L"}, {40,"XL"}
            , {10,"X"}, {9,"IX"}, {5,"V"}, {4,"IV"}, {1,"I"}
        };
        while(num) {
            for(int i = 0; i <= 12; i++){
                while(num - v[i].first >=0){
                    num -= v[i].first;
                    ss += v[i].second;
                }
            }
        }
        return ss;
    }
};