Número romano para inteiro
A missão
Problema
O catálogo de um museu guarda anos como números romanos e precisa deles como inteiros. Os símbolos são I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 e M = 1.000, escritos do maior para o menor e somados, exceto quando um símbolo menor aparece logo antes de um maior: nesse caso ele é subtraído, como em IV = 4 ou CM = 900. Dado um número romano válido para um valor de 1 a 3.999, retorne o valor dele.
Exemplos
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ê: edge case: todo o número romano é um único par subtrativo
Dicas
0 / 3
Comece com um dicionário de cada símbolo para o seu valor. Na maior parte das vezes, você só soma os valores.
Um símbolo é subtraído exatamente quando o símbolo logo depois dele vale mais. Você só precisa olhar um caractere à frente.
Percorra a string. Some o valor de cada símbolo, a menos que o próximo símbolo seja maior; nesse caso, subtraia-o. O último símbolo é sempre somado.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- the numeral is valid
- 1 ≤ value ≤ 3999
Solução
Cada símbolo soma ou subtrai o próprio valor, e qual dos dois depende só do vizinho à direita: um símbolo menor antes de um maior é subtraído, e qualquer outro é somado. Então basta uma única passada da esquerda para a direita, olhando um caractere à frente, e nenhuma tabela especial para pares como CM ou XC é necessária. O último símbolo não tem vizinho e é sempre somado. O tempo é O(n) para um número romano de n símbolos, e o espaço é 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")) # -> 4Travou na ideia, e não no código? O básico de strings explica isso.