Целое число в римскую запись

Условие

Дано целое число num в диапазоне от 1 до 3999. Преобразовать его в строковое представление римскими цифрами согласно следующим правилам:

mathematica Символ Значение I 1 V 5 X 10 L 50 C 100 D 500 M 1000

Применяются правила вычитания: 4 записывается как IV (5 − 1) 9 — как IX (10 − 1) 40 — как XL (50 − 10) 90 — как XC (100 − 10) 400 — как CD (500 − 100) 900 — как CM (1000 − 100) Преобразование должно учитывать разрядность (единицы, десятки, сотни, тысячи).

Input: num = 3749 Output: "MMMDCCXLIX"

Input: num = 58 Output: "LVIII"

Input: num = 1994 Output: "MCMXCIV"

class Solution {
    public String intToRoman(int num) {

    }
}

Ответ

Перебирайте римские обозначения от большего к меньшему, включая пары CM, CD, XC, XL, IX и IV. Пока значение помещается в остаток, дописывайте символ и вычитайте его стоимость.

public String intToRoman(int num) {
    if (num < 1 || num > 3999) throw new IllegalArgumentException();
    int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
    String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
    StringBuilder out = new StringBuilder();
    for (int i = 0; i < values.length; i++) {
        while (num >= values[i]) {
            out.append(symbols[i]);
            num -= values[i];
        }
    }
    return out.toString();
}

Для фиксированного диапазона время и память ограничены константой. Вычитательные пары обрабатываются раньше одиночных меньших символов, поэтому не возникают записи вроде IIII вместо IV.