Conversão de romano para inteiro
Experimente no GfG Practice 
Saída
Saída
Dada uma string s representando um numeral romano, encontre seu valor inteiro correspondente.
Os algarismos romanos são formados usando os seguintes símbolos: I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 e M = 1000.
Os números são normalmente formados combinando esses símbolos da esquerda para a direita, adicionando ou subtraindo seus valores com base em regras específicas.
Como funciona a conversão?
- Se um símbolo de valor menor vier antes de subtrairmos. Caso contrário, adicionamos.
- Em IV I vem antes de V e V tem um valor maior 5. Portanto, nosso resultado é 5 - 1 = 4.
- Em VI V vem antes de I e I tem um valor menor 1. Portanto, nosso resultado é 5 + 1 = 6.
- Em II temos os mesmos valores então somamos e obtemos 1 + 1 = 2
- No caso de mais de 2 caracteres, percorremos da esquerda para a direita e agrupamos apenas quando vemos um caractere de valor maior após um caractere de valor menor. Por exemplo MXVII é 1000 + 10 + 5 + 1 + 1 = 1017. E XLVII é (50 - 10) + 5 + 1 + 1 = 47. Observe que L é maior e vem depois de X.
Exemplos:
Entrada: s = 'IX'
Saída: 9
Explicação: IX é um símbolo romano que representa 10 - 1 = 9Entrada: s = 'XL'
Saída: 40
Explicação: XL é um símbolo romano que representa 50 - 10 = 40Entrada: s = 'MCMIV'
Saída: 1904
Explicação: M é 1000 CM é 1000 - 100 = 900 e IV é 4. Portanto, temos o total de 1000 + 900 + 4 = 1904
Índice
- [Abordagem Esperada 1] Usando Comparação Iterativa - O(n) tempo e O(1) espaço
- [Abordagem esperada 2] Usando Hashing - tempo O(n) e espaço O(1)
[Abordagem Esperada 1] Usando Comparação Iterativa - O(n) tempo e O(1) espaço
C++A ideia para converter um numeral romano em um inteiro é percorrer a string da esquerda para a direita. Para cada símbolo compare-o com o próximo símbolo (se existir). Se o símbolo atual for maior ou igual ao próximo símbolo, adicione seu valor ao resultado. Caso contrário, subtraia o seu valor do valor do próximo símbolo e adicione o resultado ao total e pule o próximo símbolo.
#include using namespace std ; // this function returns value of a Roman symbol int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return -1 ; } // returns decimal value of roman numeral int romanToDecimal ( string & s ) { int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // get value of current symbol int s1 = value ( s [ i ]); // Compare with the next symbol if it exists if ( i + 1 < s . length ()) { int s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } int main () { string s = 'IX' ; cout < < romanToDecimal ( s ) < < endl ; return 0 ; }
Java class GfG { // this function returns value of a Roman symbol static int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral static int romanToDecimal ( String s ) { int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { //get value of current symbol int s1 = value ( s . charAt ( i )); // compare with the next symbol if it exists if ( i + 1 < s . length ()) { int s2 = value ( s . charAt ( i + 1 )); // If current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } public static void main ( String [] args ) { String s = 'IX' ; System . out . println ( romanToDecimal ( s )); } }
Python # this function returns value of a Roman symbol def value ( r ): if r == 'I' : return 1 if r == 'V' : return 5 if r == 'X' : return 10 if r == 'L' : return 50 if r == 'C' : return 100 if r == 'D' : return 500 if r == 'M' : return 1000 return - 1 # returns decimal value of roman numeral def romanToDecimal ( s ): res = 0 i = 0 while i < len ( s ): # get value of current symbol s1 = value ( s [ i ]) # compare with the next symbol if it exists if i + 1 < len ( s ): s2 = value ( s [ i + 1 ]) # if current value is greater or equal # add it to result if s1 >= s2 : res += s1 else : # else add the difference and # skip next symbol res += ( s2 - s1 ) i += 1 else : res += s1 i += 1 return res if __name__ == '__main__' : s = 'IX' print ( romanToDecimal ( s ))
C# using System ; class GfG { // this function returns value of a Roman symbol static int value ( char r ) { if ( r == 'I' ) return 1 ; if ( r == 'V' ) return 5 ; if ( r == 'X' ) return 10 ; if ( r == 'L' ) return 50 ; if ( r == 'C' ) return 100 ; if ( r == 'D' ) return 500 ; if ( r == 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral static int romanToDecimal ( string s ) { int res = 0 ; for ( int i = 0 ; i < s . Length ; i ++ ) { // get value of current symbol int s1 = value ( s [ i ]); // compare with the next symbol if it exists if ( i + 1 < s . Length ) { int s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and skip // next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } static void Main () { string s = 'IX' ; Console . WriteLine ( romanToDecimal ( s )); } }
JavaScript // this function returns value of a Roman symbol function value ( r ) { if ( r === 'I' ) return 1 ; if ( r === 'V' ) return 5 ; if ( r === 'X' ) return 10 ; if ( r === 'L' ) return 50 ; if ( r === 'C' ) return 100 ; if ( r === 'D' ) return 500 ; if ( r === 'M' ) return 1000 ; return - 1 ; } // returns decimal value of roman numeral function romanToDecimal ( s ) { let res = 0 ; for ( let i = 0 ; i < s . length ; i ++ ) { // get value of current symbol let s1 = value ( s [ i ]); // compare with the next symbol if it exists if ( i + 1 < s . length ) { let s2 = value ( s [ i + 1 ]); // if current value is greater or equal // add it to result if ( s1 >= s2 ) { res += s1 ; } else { // else add the difference and // skip next symbol res += ( s2 - s1 ); i ++ ; } } else { res += s1 ; } } return res ; } // Driver Code let s = 'IX' ; console . log ( romanToDecimal ( s ));
Saída
9
[Abordagem esperada 2] Usando Hashing - tempo O(n) e espaço O(1)
C++Podemos usar um mapa hash ou dicionário para armazenar os valores dos símbolos romanos. E para resolver o problema temos que percorrer a string e para cada símbolo verificar se o valor atual é menor que o próximo valor. Nesse caso, subtraia o valor atual do próximo valor e adicione o resultado ao total. Caso contrário, adicione o valor atual ao total.
#include #include using namespace std ; int romanToDecimal ( string & s ) { unordered_map < char int > romanMap = {{ 'I' 1 } { 'V' 5 } { 'X' 10 } { 'L' 50 } { 'C' 100 } { 'D' 500 } { 'M' 1000 }}; int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length () && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } int main () { string s = 'IX' ; cout < < romanToDecimal ( s ) < < endl ; return 0 ; }
Java import java.util.HashMap ; class GfG { static int romanToDecimal ( String s ) { HashMap < Character Integer > romanMap = new HashMap <> (); romanMap . put ( 'I' 1 ); romanMap . put ( 'V' 5 ); romanMap . put ( 'X' 10 ); romanMap . put ( 'L' 50 ); romanMap . put ( 'C' 100 ); romanMap . put ( 'D' 500 ); romanMap . put ( 'M' 1000 ); int res = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length () && romanMap . get ( s . charAt ( i )) < romanMap . get ( s . charAt ( i + 1 ))) { res += romanMap . get ( s . charAt ( i + 1 )) - romanMap . get ( s . charAt ( i )); // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap . get ( s . charAt ( i )); } } return res ; } public static void main ( String [] args ) { String s = 'IX' ; System . out . println ( romanToDecimal ( s )); } }
Python def romanToDecimal ( s ): romanMap = { 'I' : 1 'V' : 5 'X' : 10 'L' : 50 'C' : 100 'D' : 500 'M' : 1000 } res = 0 i = 0 while i < len ( s ): # if the current value is less than the next value # subtract current from next and add to res if i + 1 < len ( s ) and romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]: res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]] # skip the next symbol i += 1 else : # otherwise add the current value to res res += romanMap [ s [ i ]] i += 1 return res if __name__ == '__main__' : s = 'IX' print ( romanToDecimal ( s ))
C# using System ; using System.Collections.Generic ; class GfG { static int romanToDecimal ( string s ) { // create a map to store the Roman numeral values Dictionary < char int > romanMap = new Dictionary < char int > { { 'I' 1 } { 'V' 5 } { 'X' 10 } { 'L' 50 } { 'C' 100 } { 'D' 500 } { 'M' 1000 } }; int res = 0 ; for ( int i = 0 ; i < s . Length ; i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . Length && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } static void Main () { string s = 'IX' ; Console . WriteLine ( romanToDecimal ( s )); } }
JavaScript function romanToDecimal ( s ) { // create a map to store the Roman numeral values const romanMap = { 'I' : 1 'V' : 5 'X' : 10 'L' : 50 'C' : 100 'D' : 500 'M' : 1000 }; let res = 0 ; for ( let i = 0 ; i < s . length ; i ++ ) { // if the current value is less than the next value // subtract current from next and add to res if ( i + 1 < s . length && romanMap [ s [ i ]] < romanMap [ s [ i + 1 ]]) { res += romanMap [ s [ i + 1 ]] - romanMap [ s [ i ]]; // skip the next symbol i ++ ; } else { // otherwise add the current value to res res += romanMap [ s [ i ]]; } } return res ; } // Driver Code let s = 'IX' ; console . log ( romanToDecimal ( s ));
Saída
9
