Почему это работает
- Одними символами меньше какого-то значения правильная запись до него не дотягивает: меньше CM = 900 самое большое — DCCCXCIX = 899. Поэтому если значение помещается, запись обязана взять его сейчас: меньшие его не наберут.
- Пары CM, CD, XC, XL, IX и IV стоят в таблице как отдельные значения. Благодаря им жадности не нужны четыре одинаковых символа: 94 — это XC + IV, а не LXXXX + IIII.
- num только уменьшается, а таблица проходится один раз сверху вниз, поэтому символы выходят от больших к меньшим, как и требует римская запись.
Сложность
Время O(1): в таблице 13 значений, и ни один символ не пишется больше трёх раз подряд, поэтому символов выходит не больше 15. Память O(1), не считая ответа.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗