Roman to Integer

+10

Les chiffres romains utilisent sept symboles : I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 et M = 1000. Les symboles sont écrits du plus grand au plus petit et additionnés, sauf dans six paires soustractives où un symbole plus petit vient en premier et est soustrait du plus grand : IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 et CM = 900.

On vous donne un chiffre romain valide s. Renvoyez l’entier qu’il représente.

Fonction

romanToInt(s: string) → integer

sstring: un chiffre romain valide en majuscules
Renvoieinteger: la valeur du nombre, de 1 à 3999

Contraintes

1 ≤ s.length ≤ 15
s ne contient que les caractères I, V, X, L, C, D et M.
s est un chiffre romain valide pour une valeur comprise entre 1 et 3999.

Exemples

Entrée: s = "XXVII"
Sortie: 27
Explication: XX vaut 10 + 10, V vaut 5 et II vaut 1 + 1, donc le total est 27. Aucun symbole n'est suivi d'un symbole plus grand, donc chaque symbole est additionné.

Entrée: s = "CDXLIV"
Sortie: 444
Explication: Le nombre est composé de trois paires soustractives consécutives : CD vaut 400, XL vaut 40 et IV vaut 4, ce qui donne 444.

Entrée: s = "MCDXCII"
Sortie: 1492
Explication: M vaut 1000, CD vaut 400, XC vaut 90 et II vaut 2, donc le nombre est 1492. Les paires et les symboles isolés se combinent librement.

+22 tests cachés à la soumission

Pour aller plus loin

Peux-tu écrire l’opération inverse, qui convertit un entier compris entre 1 et 3999 en chiffre romain ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La majeure partie d’un nombre est une simple somme ; tout le problème consiste donc à repérer les six paires soustractives. Tu peux les rechercher sous forme de jetons de deux lettres, ou appliquer la règle qui couvre les six cas : un symbole dont la valeur est inférieure à celle de son voisin de droite est soustrait. Dans les deux cas, un seul parcours d’au plus 15 caractères suffit pour obtenir la réponse.

Lire les paires soustractives comme des jetons

Intuition

Considère le nombre comme une suite de jetons. La plupart des jetons sont constitués d’un seul symbole, et six sont constitués de deux symboles : IV, IX, XL, XC, CD et CM. Découpe la chaîne en ces jetons, additionne leurs valeurs, et tu obtiens le nombre.

À chaque position, regarde d’abord les deux caractères suivants. S’ils forment l’une des six paires, ajoute la valeur de la paire et avance de deux caractères. Sinon, ajoute la valeur du symbole seul et avance d’un caractère. MCDXCII se décompose en M, CD, XC, I, I : 1000 + 400 + 90 + 1 + 1 = 1492.

La vérification de la paire doit se faire en premier. Si tu lis le X de XC tout seul, tu ajoutes 10, puis 100, et tu obtiens 110 au lieu de 90. Cette vérification est également sûre : dans un nombre valide, un symbole plus petit se trouve juste avant un symbole plus grand uniquement dans l’une de ces six paires, donc chaque paire que tu trouves est bien réelle.

Chaque étape consomme un ou deux caractères, donc la boucle s’exécute au maximum 15 fois. Les deux tableaux ont une taille fixe, donc l’espace supplémentaire est constant.

Algorithme

Crée un tableau pour les six paires et un pour les sept symboles uniques.
Commence à l’indice 0 avec un total de 0.
Si les deux caractères à l’indice forment une paire, ajoute la valeur de la paire et avance l’indice de 2.
Sinon, ajoute la valeur du symbole unique et avance l’indice de 1.
Lorsque l’indice dépasse la fin, retourne le total.

def romanToInt(s):
    pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
    singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    i = 0
    while i < len(s):
        two = s[i:i + 2]
        if two in pairs:
            total += pairs[two]
            i += 2
        else:
            total += singles[s[i]]
            i += 1
    return total

Comparez chaque symbole au suivant

Intuition

Examinez à nouveau les six paires. Dans chacune d’elles, le premier symbole vaut moins que le second, et la paire vaut le second moins le premier. Vous pouvez donc supprimer le tableau des paires et appliquer une seule règle : si un symbole vaut moins que celui qui le suit, soustrayez-le ; sinon, additionnez-le. CM devient -100 + 1000 = 900, soit la même valeur que celle obtenue par la lecture des jetons.

Parcourez MCDXCII. M est suivi d’un C plus petit, donc ajoutez 1000. C est suivi d’un D plus grand, donc soustrayez 100 : le total est de 900. Ajoutez D pour atteindre 1400. X est suivi d’un C plus grand, donc soustrayez 10 : 1390. Ajoutez C : 1490. Le premier I est suivi d’un I égal, donc ajoutez-le : 1491. Le dernier I n’a pas de voisin, donc ajoutez-le également : 1492.

La comparaison doit être strictement inférieure. Les symboles voisins égaux sont toujours additionnés, ce qui explique pourquoi II vaut 2 et XX vaut 20. La règle est correcte pour la même raison que la lecture des jetons : dans un numéral valide, un symbole plus petit ne précède un symbole plus grand que lorsqu’il constitue la première moitié d’une paire soustractive.

Vous examinez chaque caractère une seule fois et conservez un total courant ; le temps d’exécution est donc O(n) et l’espace supplémentaire est O(1). Cette version ne nécessite que les sept valeurs des symboles et une comparaison par caractère.

Algorithme

Stockez la valeur de chacun des sept symboles.
Parcourez les indices de s avec un total cumulé qui commence à 0.
Si le symbole suivant existe et vaut plus que le symbole actuel, soustrayez la valeur actuelle.
Sinon, ajoutez la valeur actuelle.
Renvoyez le total après la boucle.

def romanToInt(s):
    values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i in range(len(s)):
        value = values[s[i]]
        # A symbol worth less than the one after it is subtracted, like the I in IV.
        if i + 1 < len(s) and value < values[s[i + 1]]:
            total -= value
        else:
            total += value
    return total

Pièges et cas limites

La règle est courte, les erreurs concernent donc ses cas limites.

Utiliser « inférieur ou égal » au lieu de « strictement inférieur ». Alors II donne 0 et XX donne 0, car le premier symbole est soustrait dans chaque cas.
Lire le symbole suivant sur le dernier caractère. s[i+1] n’existe pas à cet endroit ; vérifie d’abord i+1 par rapport à la longueur, et ajoute toujours le dernier symbole.
Dans la version avec des jetons, essayer les symboles seuls avant les paires. XC est alors lu comme 10 + 100 = 110.
Repérer la paire uniquement à son second symbole. Si tu as déjà ajouté le I de IV, tu dois le soustraire deux fois : 1 + 5 - 2 × 1 = 4. Comparer avec le symbole suivant évite cette correction.
Oublier que les chaînes Lua et R commencent à l’indice 1, donc le dernier symbole se trouve à #s ou nchar(s).

Questions fréquentes4

Quelle est la complexité temporelle de la conversion des chiffres romains en entier ?

Les deux approches parcourent chaque caractère une seule fois, donc le temps d’exécution est de O(n) pour un chiffre de n caractères. L’espace supplémentaire est de O(1), car les tables de correspondance ont une taille fixe. Un chiffre compris entre 1 et 3999 comporte au plus 15 caractères, donc en pratique, le travail est minime.

Pourquoi soustrait-on un symbole plus petit que le suivant ?

C’est ainsi que se forment les six paires soustractives. Dans IV, IX, XL, XC, CD et CM, un symbole plus petit précède un symbole plus grand, et la paire vaut le plus grand moins le plus petit. Soustraire le premier symbole et ajouter le second donne exactement cette valeur, et dans aucun autre endroit d’un nombre valide le symbole plus petit ne précède un symbole plus grand.

Peux-tu convertir un chiffre romain de droite à gauche ?

Oui. Parcourez les symboles du dernier au premier et mémorisez la valeur du symbole lu précédemment, celui qui se trouve à droite. Si le symbole actuel vaut moins que celui-là, soustrayez-le ; sinon, additionnez-le. C’est la même règle que celle de la version de gauche à droite, vue de l’autre côté.

Cette solution vérifie-t-elle que le chiffre est valide ?

Non. L’énoncé garantit un numéral valide, donc le code ne fait qu’additionner et soustraire. Avec une chaîne invalide comme IIII ou VV, il renvoie quand même un nombre, 4 et 10. Pour valider, convertissez le résultat en numéral et comparez-le à l’entrée.

Python

def romanToInt(s):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "XXVII"

Attendu