13. Roman to Integer

Условие задачи

Римские цифры представлены семью различными символами:

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

Примеры:

• 2 записывается как II (два раза по 1).
• 12 записывается как XII (X + II).
• 27 записывается как XXVII (XX + V + II).

Обычно римские цифры записываются от большего к меньшему слева направо. Однако есть исключения, связанные с вычитанием:

• 4 записывается как IV, а не IIII (I перед V значит 5 − 1).
• 9 записывается как IX.

Случаи использования вычитания:

• I перед V (5) и X (10) → 4 и 9
• X перед L (50) и C (100) → 40 и 90
• C перед D (500) и M (1000) → 400 и 900

Формально задача звучит так:

Дан римский символ (строка). Преобразуйте его в целое число.

Решение: проход по строке с учётом следующего символа

Идея

Алгоритм идёт слева направо по строке. Для каждого символа:

• Берём его значение.
• Смотрим на следующий символ (если он есть).
• Если следующий символ больше текущего — значит, используется правило вычитания: добавляем разницу и пропускаем следующий символ.
• Иначе просто добавляем текущее значение.

Таким образом, за один проход по строке получаем итоговое число.

var romanIntDict = map[byte]int{
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000,
}
 
func romanToInt(s string) int {
    res := 0
    for i := 0; i < len(s); i++ {
        c := romanIntDict[s[i]]
        n := 0
        if i != len(s) - 1 {
            n = romanIntDict[s[i + 1]]
        }
        if n > c {
            res += n - c
            i++
            continue
        }
        res += c
    }
    return res
}

Решение: проход справа налево

Идея

Идея: римские числа складываются справа налево.

• Если текущий символ меньше предыдущего (соседа справа) → вычитаем.
• Иначе → прибавляем.

var romanIntDict = map[byte]int{
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000,
}
 
func romanToInt(s string) int {
    res := 0
    prev := 0
    for i := len(s) - 1; i >= 0; i-- {
        cur := romanIntDict[s[i]]
        if cur < prev {
            res -= cur
        } else {
            res += cur
        }
        prev = cur
    }
    return res
}

Плюс: нет необходимости отдельно смотреть следующий символ.
Минус: чуть менее интуитивно при первом чтении.

Решение: словарь со специальными парами

Идея

Вместо логики “сравнивать текущий и следующий символ”, можно заранее завести словарь с комбинациями вычитаний (IV, IX, XL, …).
Тогда алгоритм идёт слева направо:

• если встречаем двухсимвольную комбинацию → берём её значение и двигаемся на 2 шага;
• иначе берём одиночный символ.

var romanIntDict = map[string]int{
    "I": 1, "V": 5, "X": 10, "L": 50,
    "C": 100, "D": 500, "M": 1000,
    "IV": 4, "IX": 9, "XL": 40, "XC": 90,
    "CD": 400, "CM": 900,
}
 
func romanToInt(s string) int {
    res := 0
    for i := 0; i < len(s); {
        if i+1 < len(s) {
            if val, ok := romanIntDict[s[i:i+2]]; ok {
                res += val
                i += 2
                continue
            }
        }
        res += romanIntDict[string(s[i])]
        i++
    }
    return res
}

Плюс: явная обработка вычитательных случаев.
Минус: больше данных в словаре.