Конвертация римских чисел

Конвертация римских чисел в арабские

Это задача на обработку строк с правилами вычитания. Нужно правильно обработать случаи, когда меньшее число стоит перед большим (IV, IX, XL, XC, CD, CM).

Решение 1: Слева направо (самое простое)

Алгоритм: идём слева направо, если текущее число меньше следующего — вычитаем, иначе — добавляем.

def roman_to_int(s: str) -> int:
    # Соответствие символов их значениям
    roman_values = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    
    total = 0
    
    for i in range(len(s)):
        current_value = roman_values[s[i]]
        
        # Если следующий символ больше текущего
        if i + 1 < len(s) and roman_values[s[i + 1]] > current_value:
            # Вычитаем текущее значение
            total -= current_value
        else:
            # Иначе добавляем
            total += current_value
    
    return total

# Примеры
print(roman_to_int("III"))      # 3
print(roman_to_int("IV"))       # 4
print(roman_to_int("IX"))       # 9
print(roman_to_int("LVIII"))    # 58
print(roman_to_int("MCMXCIV"))  # 1994

Как работает на примере "MCMXCIV" (1994):

M:    1000 (следующий X < M, добавляем)      total = 1000
C:     100 (следующий M > C, вычитаем!)      total = 900
M:    1000 (следующий X < M, добавляем)      total = 1900
X:      10 (следующий C > X, вычитаем!)      total = 1890
C:     100 (следующий I < C, добавляем)      total = 1990
I:       1 (нет следующего, добавляем)       total = 1991
V:       5 (нет следующего, добавляем)       total = 1996
V:       5 (нет следующего, но это IV!)      total = 1994

Подождите, выше ошибка. Давайте пересчитаем:

M:    1000 (i=0, s[1]=C, 100 < 1000, добавляем)  total = 1000
C:     100 (i=1, s[2]=M, 1000 > 100, вычитаем)   total = 900
M:    1000 (i=2, s[3]=X, 10 < 1000, добавляем)   total = 1900
X:      10 (i=3, s[4]=C, 100 > 10, вычитаем)     total = 1890
C:     100 (i=4, s[5]=I, 1 < 100, добавляем)     total = 1990
I:       1 (i=5, s[6]=V, 5 > 1, вычитаем)        total = 1989
V:       5 (i=6, конец, добавляем)               total = 1994

Сложность:

• Время: O(n) где n — длина строки
• Память: O(1) — только словарь с 7 элементами

Решение 2: Справа налево (элегантнее)

Идём с конца, если текущее число меньше предыдущего — вычитаем, иначе — добавляем.

def roman_to_int_rtl(s: str) -> int:
    roman_values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 
                    'C': 100, 'D': 500, 'M': 1000}
    
    total = 0
    prev_value = 0
    
    # Идём с конца
    for char in reversed(s):
        current_value = roman_values[char]
        
        # Если текущее меньше предыдущего — вычитаем
        if current_value < prev_value:
            total -= current_value
        else:
            total += current_value
        
        prev_value = current_value
    
    return total

print(roman_to_int_rtl("MCMXCIV"))  # 1994

Как работает справа налево на "IV":

V: 5 (prev=0, 5 >= 0, добавляем)        total = 5, prev = 5
I: 1 (prev=5, 1 < 5, вычитаем!)         total = 4, prev = 1
Результат: 4

Это более элегантно потому что:

• Логика проще
• Не нужно смотреть в будущее

Решение 3: С использованием list comprehension

def roman_to_int_compact(s: str) -> int:
    values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    return sum(
        -values[s[i]] if i + 1 < len(s) and values[s[i]] < values[s[i+1]]
        else values[s[i]]
        for i in range(len(s))
    )

print(roman_to_int_compact("MCMXCIV"))  # 1994

Красиво, но менее читаемо.

Все правила вычитания

Меньшее число может стоять перед большим только в следующих случаях:

# Составляющие
IV = 4       # I (1) перед V (5)
IX = 9       # I (1) перед X (10)
XL = 40      # X (10) перед L (50)
XC = 90      # X (10) перед C (100)
CD = 400     # C (100) перед D (500)
CM = 900     # C (100) перед M (1000)

# Примеры комбинаций
1994 = 1000 + 900 + 90 + 4 = M + CM + XC + IV = MCMXCIV
3999 = 3000 + 900 + 90 + 9 = MMM + CM + XC + IX = MMMCMXCIX

Решение с явной обработкой вычитаний

def roman_to_int_explicit(s: str) -> int:
    # Одновременно обрабатываем символы и пары вычитания
    replacements = {
        'IV': 4, 'IX': 9,
        'XL': 40, 'XC': 90,
        'CD': 400, 'CM': 900
    }
    
    # Заменяем все пары вычитания на их значения
    for pair, value in replacements.items():
        s = s.replace(pair, f'${value}$')  # Экранируем плейсхолдер
    
    # Теперь парсим оставшиеся символы
    values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    i = 0
    
    while i < len(s):
        if s[i] == '$':
            # Это плейсхолдер для пары вычитания
            j = i + 1
            while s[j] != '$':
                j += 1
            total += int(s[i+1:j])
            i = j + 1
        else:
            total += values[s[i]]
            i += 1
    
    return total

Это сложнее, не рекомендуется.

Тестовые случаи

def test_roman_to_int():
    assert roman_to_int("I") == 1
    assert roman_to_int("II") == 2
    assert roman_to_int("III") == 3
    assert roman_to_int("IV") == 4
    assert roman_to_int("V") == 5
    assert roman_to_int("IX") == 9
    assert roman_to_int("X") == 10
    assert roman_to_int("LVIII") == 58      # 50 + 5 + 3
    assert roman_to_int("MCMXCIV") == 1994  # 1000 + 900 + 90 + 4
    assert roman_to_int("MMMCMXCIX") == 3999
    print("Все тесты пройдены!")

test_roman_to_int()

Сложность и сравнение

Рекомендация

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

def roman_to_int(s: str) -> int:
    values = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total, prev = 0, 0
    
    for char in reversed(s):
        val = values[char]
        total += val if val >= prev else -val
        prev = val
    
    return total

Всего 6 строк и полностью понятно!