Roman to Integer

Условие

Римские цифры состоят из следующих символов:

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

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

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

• I может быть перед V (5) и X (10), чтобы создать 4 и 9.
• X может быть перед L (50) и C (100), чтобы создать 40 и 90.
• C может быть перед D (500) и M (1000), чтобы создать 400 и 900.

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

Примеры

Input: s = "III"

Output: 3

Explanation: III = 3.

Input: s = "LVIII"

Output: 58

Explanation: L = 50, V = 5, III = 3.

Input: s = "MCMXCIV"

Output: 1994

Explanation: M = 1000, CM = 900, XC = 90 и IV = 4.

Решение

fun romanToInt(s: String): Int {
    // Определяем карту значений римских символов
    val romanToIntMap = mapOf(
        'I' to 1,
        'V' to 5,
        'X' to 10,
        'L' to 50,
        'C' to 100,
        'D' to 500,
        'M' to 1000
    )
    
    var result = 0
    var prevValue = 0

    // Проходим по всем символам строки справа налево
    for (char in s.reversed()) {
        // Получаем значение текущего римского символа
        val currentValue = romanToIntMap[char] ?: 0
        
        // Если предыдущее значение больше текущего, значит нужно вычесть текущее значение
        if (currentValue < prevValue) {
            result -= currentValue
        } else {
            // Иначе добавляем текущее значение к результату
            result += currentValue
        }
        
        // Обновляем предыдущее значение
        prevValue = currentValue
    }

    return result
}

Временная сложность

O(n), где n — длина входной строки. Мы проходим по строке один раз.

Пространственная сложность

O(1), так как мы используем фиксированное количество дополнительных переменных.