Algorithmics: хакаем алгоритми… on Telegram: “Преобразование римских чисел в арабские Давайте…”

Преобразование римских чисел в арабские

Давайте отдохнем от сложных задач и рассмотрим классическую легкую с собеседований.

Сложность: 🟢 Легкая

ℹ️ Описание

Напишите функцию, которая принимает на вход римское число в виде строки и возвращает в ответе ее арабское представление.

⚠️ Ограничения

🔹 Длина строки с римским числом может быть в диапазоне от 1 до 15
🔹Строка содержит только валидные римские цифры в верхнем регистре

1️⃣ Пример

Входящие данные: III
Ответ: 3
Объяснение: III = I + I + I = 1 + 1 + 1 = 3

2️⃣ Пример

Входящие данные: LVIII
Ответ: 58
Объяснение: LVIII = L + V + I + I + I = 50 + 5 + 1 + 1 + 1 = 58

3️⃣ Пример

Входящие данные: MCMXCIV
Ответ: 1994
Объяснение: MCMXCIV = M + (M - C) + (C - X) + (V - I) = 1000 + (1000 - 100) + (100 - 10) + (5-1) = 1994

📖 Правила формирования римских чисел

Римские цифры могут быть представлены семью разными символами: I, V, X, L, C, D и M.

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

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

Есть шесть случаев, когда используется вычитание:

🔹 I можно поставить перед V и X, чтобы получилось 4 и 9.
🔹X можно поставить перед L и C, чтобы получилось 40 и 90.
🔹C можно поставить перед D и M, чтобы получилось 400 и 900.

✅ Решение

Для решения данной задачи нам достаточно будет посимвольно пройтись по строке, преобразовать римский цифры в арабские и суммировать их. Главная сложность — учесть правила декремента (IV = 4, а не 6, так как меньшая цифра I стоит перед большей V).

Для преобразования римских цифр создадим хеш-мапу, у которой в качестве ключа будет римская цифра, а в качестве значения арабское число.


var runeToIntegerMap = map[rune]int{
    'I': 1,
    'V': 5,
    'X': 10,
    'L': 50,
    'C': 100,
    'D': 500,
    'M': 1000,
}

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


var runeToIntegerDecrementsMap = map[rune]map[rune]int{
    'I': {
        'V': 4,
        'X': 9,
    },
    'X': {
        'L': 40,
        'C': 90,
    },
    'C': {
        'D': 400,
        'M': 900,
    },
}

Таким образом, анализируя текущую и следующую цифру с помощью runeToIntegerDecrementsMap, мы сможем легко получить правильное число.

Имея эти две вспомогательные хеш-мапы нам останется только пробежаться посимвольно по строке, преобразовать римскую цифру (проверяя не только текущий, но и следующий символ) в число и суммировать получившееся число с переменной-результатом.

Посмотреть реализацию

🅾️ Оценка сложности

По времени
Чтобы преобразовать число, нам потребуется проитерироваться по всей строке длиною n. Никаких дополнительных действий, зависящих от длины строки, в алгоритме не происходит. Сложность по времени O(n)

По памяти
Сложность по памяти O(1), так как алгоритм не подразумевает выделение дополнительной памяти, зависящей от длины строки n.

#easy #strings