De número romano a entero
La misión
Problema
Un catálogo de museo guarda los años como números romanos y los necesita como enteros. Los símbolos son I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 y M = 1000, se escriben de mayor a menor y se suman, salvo que un símbolo menor colocado justo antes de uno mayor se resta, como en IV = 4 o CM = 900. Dado un número romano válido para un valor de 1 a 3999, devuelve su valor.
Ejemplos
Input: s = "LVIII"
Output: 58
Por qué: L + V + I + I + I = 50 + 5 + 3
Input: s = "MCMXCIV"
Output: 1994
Por qué: M = 1000, CM = 900, XC = 90, IV = 4
Input: s = "IV"
Output: 4
Por qué: caso límite: todo el número es un único par sustractivo
Pistas
0 / 3
Empieza con un diccionario de cada símbolo a su valor. La mayoría de las veces solo sumas los valores.
Un símbolo se resta exactamente cuando el símbolo que está justo después vale más. Solo necesitas mirar un carácter hacia adelante.
Recorre el string. Suma el valor de cada símbolo, salvo que el siguiente símbolo sea mayor; en ese caso, réstalo. El último símbolo siempre se suma.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- the numeral is valid
- 1 ≤ value ≤ 3999
Solución
Cada símbolo suma o resta su propio valor según su vecino de la derecha: un símbolo menor antes de uno mayor se resta y cualquier otro se suma. Por eso basta una pasada de izquierda a derecha mirando un carácter hacia adelante, y no hace falta una tabla especial para pares como CM o XC. El último símbolo no tiene vecino y siempre se suma. El tiempo es O(n) para un número de n símbolos y el espacio es O(1).
VALUE = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
def roman_to_int(s):
total = 0
for i, ch in enumerate(s):
v = VALUE[ch]
if i + 1 < len(s) and VALUE[s[i + 1]] > v:
total -= v # smaller before larger: subtract
else:
total += v
return total
print(roman_to_int("LVIII")) # -> 58
print(roman_to_int("MCMXCIV")) # -> 1994
print(roman_to_int("IV")) # -> 4¿Lo que te frena es la idea y no el código? Fundamentos de strings lo explica.