Algoritmos de Números Romanos: Implementación en Python, JavaScript y Java

Convertir entre números romanos y enteros es un problema clásico de programación que aparece en entrevistas de código, programación competitiva y aplicaciones del mundo real. Esta guía proporciona implementaciones optimizadas en Python, JavaScript y Java, junto con explicaciones de los algoritmos subyacentes.

Comprendiendo el Problema

Necesitamos resolver dos problemas relacionados:

1. Entero a Romano: Convertir un número arábigo (ej., 1994) a números romanos (MCMXCIV)
2. Romano a Entero: Convertir números romanos (ej., MCMXCIV) a un número arábigo (1994)

Restricciones

• Rango de entrada: 1 a 3999 (rango estándar de números romanos)
• Usar notación sustractiva estándar (IV, IX, XL, XC, CD, CM)
• Manejar todas las combinaciones válidas de números romanos

El Enfoque del Algoritmo Greedy

Ambas conversiones utilizan una estrategia de algoritmo greedy:

Entero a Romano (Greedy)

1. Crear un mapeo de valores a números romanos en orden descendente
2. Para cada par valor-numeral:
   • Usar tantos de ese numeral como sea posible
   • Restar el valor del número restante
3. Repetir hasta que el número llegue a cero

Romano a Entero (Greedy)

1. Escanear la cadena de números romanos de izquierda a derecha
2. Para cada símbolo:
   • Si es menor que el siguiente símbolo, restarlo (notación sustractiva)
   • De lo contrario, sumarlo
3. Devolver la suma acumulada

Implementación en Python

Entero a Romano

def int_to_roman(num: int) -> str:
    """
    Convert an integer to Roman numerals.

    Args:
        num: Integer between 1 and 3999

    Returns:
        Roman numeral string

    Time Complexity: O(1) - fixed number of iterations (13)
    Space Complexity: O(1) - fixed size mapping
    """
    # Mapping in descending order (including subtractive combinations)
    values = [
        (1000, 'M'),
        (900, 'CM'),
        (500, 'D'),
        (400, 'CD'),
        (100, 'C'),
        (90, 'XC'),
        (50, 'L'),
        (40, 'XL'),
        (10, 'X'),
        (9, 'IX'),
        (5, 'V'),
        (4, 'IV'),
        (1, 'I')
    ]

    result = []

    for value, numeral in values:
        count = num // value
        if count:
            result.append(numeral * count)
            num -= value * count

    return ''.join(result)

Romano a Entero

def roman_to_int(s: str) -> int:
    """
    Convert Roman numerals to an integer.

    Args:
        s: Roman numeral string

    Returns:
        Integer value

    Time Complexity: O(n) where n is the length of the string
    Space Complexity: O(1) - fixed size mapping
    """
    # Mapping of Roman symbols to values
    roman_map = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }

    total = 0
    prev_value = 0

    # Scan from right to left
    for char in reversed(s):
        value = roman_map[char]

        # If current value is less than previous, subtract it
        if value < prev_value:
            total -= value
        else:
            total += value

        prev_value = value

    return total

Ejemplos de Uso

# Entero a Romano
print(int_to_roman(1994))  # Output: MCMXCIV
print(int_to_roman(58))    # Output: LVIII
print(int_to_roman(9))     # Output: IX

# Romano a Entero
print(roman_to_int("MCMXCIV"))  # Output: 1994
print(roman_to_int("LVIII"))    # Output: 58
print(roman_to_int("IX"))       # Output: 9

Implementación en JavaScript

Entero a Romano

/**
 * Convert an integer to Roman numerals
 * @param {number} num - Integer between 1 and 3999
 * @returns {string} Roman numeral string
 *
 * Time Complexity: O(1)
 * Space Complexity: O(1)
 */
function intToRoman(num) {
    const values = [
        [1000, 'M'],
        [900, 'CM'],
        [500, 'D'],
        [400, 'CD'],
        [100, 'C'],
        [90, 'XC'],
        [50, 'L'],
        [40, 'XL'],
        [10, 'X'],
        [9, 'IX'],
        [5, 'V'],
        [4, 'IV'],
        [1, 'I']
    ];

    let result = '';

    for (const [value, numeral] of values) {
        const count = Math.floor(num / value);
        if (count) {
            result += numeral.repeat(count);
            num -= value * count;
        }
    }

    return result;
}

Romano a Entero

/**
 * Convert Roman numerals to an integer
 * @param {string} s - Roman numeral string
 * @returns {number} Integer value
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function romanToInt(s) {
    const romanMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };

    let total = 0;
    let prevValue = 0;

    // Scan from right to left
    for (let i = s.length - 1; i >= 0; i--) {
        const value = romanMap[s[i]];

        if (value < prevValue) {
            total -= value;
        } else {
            total += value;
        }

        prevValue = value;
    }

    return total;
}

Ejemplos de Uso

// Entero a Romano
console.log(intToRoman(1994));  // Output: MCMXCIV
console.log(intToRoman(58));    // Output: LVIII
console.log(intToRoman(9));     // Output: IX

// Romano a Entero
console.log(romanToInt("MCMXCIV"));  // Output: 1994
console.log(romanToInt("LVIII"));    // Output: 58
console.log(romanToInt("IX"));       // Output: 9

Implementación en Java

Entero a Romano

/**
 * Convert an integer to Roman numerals
 *
 * Time Complexity: O(1)
 * Space Complexity: O(1)
 */
public class RomanConverter {
    private static final int[] VALUES = {
        1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1
    };

    private static final String[] NUMERALS = {
        "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
    };

    public static String intToRoman(int num) {
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < VALUES.length; i++) {
            int count = num / VALUES[i];
            if (count > 0) {
                result.append(NUMERALS[i].repeat(count));
                num -= VALUES[i] * count;
            }
        }

        return result.toString();
    }
}

Romano a Entero

/**
 * Convert Roman numerals to an integer
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
public class RomanConverter {
    private static final Map<Character, Integer> ROMAN_MAP = Map.of(
        'I', 1,
        'V', 5,
        'X', 10,
        'L', 50,
        'C', 100,
        'D', 500,
        'M', 1000
    );

    public static int romanToInt(String s) {
        int total = 0;
        int prevValue = 0;

        // Scan from right to left
        for (int i = s.length() - 1; i >= 0; i--) {
            int value = ROMAN_MAP.get(s.charAt(i));

            if (value < prevValue) {
                total -= value;
            } else {
                total += value;
            }

            prevValue = value;
        }

        return total;
    }
}

Ejemplos de Uso

public class Main {
    public static void main(String[] args) {
        // Entero a Romano
        System.out.println(RomanConverter.intToRoman(1994));  // Output: MCMXCIV
        System.out.println(RomanConverter.intToRoman(58));    // Output: LVIII
        System.out.println(RomanConverter.intToRoman(9));     // Output: IX

        // Romano a Entero
        System.out.println(RomanConverter.romanToInt("MCMXCIV"));  // Output: 1994
        System.out.println(RomanConverter.romanToInt("LVIII"));    // Output: 58
        System.out.println(RomanConverter.romanToInt("IX"));       // Output: 9
    }
}

Análisis de Complejidad

Complejidad Temporal

Operación	Complejidad	Explicación
Entero a Romano	O(1)	Número fijo de iteraciones (13 pares valor-numeral)
Romano a Entero	O(n)	Una pasada por la cadena de entrada de longitud n

Complejidad Espacial

Ambos algoritmos usan O(1) espacio ya que:

• El mapeo tiene un tamaño fijo (13 o 7 entradas)
• No se crean estructuras de datos adicionales proporcionales a la entrada

Casos Extremos y Validación

Casos Extremos Importantes

# Valores mínimos y máximos
assert int_to_roman(1) == "I"
assert int_to_roman(3999) == "MMMCMXCIX"

# Combinaciones sustractivas
assert int_to_roman(4) == "IV"
assert int_to_roman(9) == "IX"
assert int_to_roman(40) == "XL"
assert int_to_roman(90) == "XC"
assert int_to_roman(400) == "CD"
assert int_to_roman(900) == "CM"

# Números complejos
assert int_to_roman(1994) == "MCMXCIV"
assert int_to_roman(2024) == "MMXXIV"

Validación de Entrada

def int_to_roman_safe(num: int) -> str:
    """Versión con validación de entrada"""
    if not isinstance(num, int):
        raise TypeError("La entrada debe ser un entero")
    if num < 1 or num > 3999:
        raise ValueError("El número debe estar entre 1 y 3999")
    return int_to_roman(num)

def roman_to_int_safe(s: str) -> int:
    """Versión con validación de entrada"""
    if not isinstance(s, str):
        raise TypeError("La entrada debe ser una cadena")
    if not s:
        raise ValueError("La cadena no puede estar vacía")

    valid_chars = set('IVXLCDM')
    if not all(c in valid_chars for c in s):
        raise ValueError("Caracteres romanos inválidos")

    return roman_to_int(s)

Optimizaciones y Variaciones

1. Usando Diccionarios (Python)

def int_to_roman_dict(num: int) -> str:
    """Versión alternativa usando diccionario"""
    thousands = ["", "M", "MM", "MMM"]
    hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]

    return (thousands[num // 1000] +
            hundreds[(num % 1000) // 100] +
            tens[(num % 100) // 10] +
            ones[num % 10])

2. Enfoque Recursivo (JavaScript)

function intToRomanRecursive(num) {
    const values = [
        [1000, 'M'], [900, 'CM'], [500, 'D'], [400, 'CD'],
        [100, 'C'], [90, 'XC'], [50, 'L'], [40, 'XL'],
        [10, 'X'], [9, 'IX'], [5, 'V'], [4, 'IV'], [1, 'I']
    ];

    for (const [value, numeral] of values) {
        if (num >= value) {
            return numeral + intToRomanRecursive(num - value);
        }
    }

    return '';
}

3. Enfoque de Escaneo Hacia Adelante (Java)

public static int romanToIntForward(String s) {
    int total = 0;

    for (int i = 0; i < s.length(); i++) {
        int current = ROMAN_MAP.get(s.charAt(i));

        // Mirar hacia adelante para la notación sustractiva
        if (i + 1 < s.length()) {
            int next = ROMAN_MAP.get(s.charAt(i + 1));
            if (current < next) {
                total -= current;
                continue;
            }
        }

        total += current;
    }

    return total;
}

Comparación de Rendimiento

Benchmarks (1 millón de operaciones)

Lenguaje	Entero a Romano	Romano a Entero
Python	~2.5s	~1.8s
JavaScript (Node.js)	~0.8s	~0.6s
Java	~0.3s	~0.2s

Nota: Los benchmarks son aproximados y varían según el hardware

Consejos de Optimización

1. Pre-calcular valores comunes: Cachear conversiones frecuentes
2. Usar StringBuilder/arrays: Evitar concatenación de cadenas en bucles
3. Validación temprana: Verificar entradas antes del procesamiento
4. Evitar recursión: Los enfoques iterativos son más rápidos

Problemas Comunes y Soluciones

Problema 1: Orden Incorrecto de Mapeo

# ❌ Incorrecto - orden ascendente
values = [(1, 'I'), (5, 'V'), (10, 'X')]  # No funcionará

# ✅ Correcto - orden descendente
values = [(10, 'X'), (5, 'V'), (1, 'I')]

Problema 2: Olvidar Combinaciones Sustractivas

# ❌ Incorrecto - falta notación sustractiva
values = [(1000, 'M'), (500, 'D'), (100, 'C')]  # 900 se convierte en DCCCC

# ✅ Correcto - incluye todas las combinaciones sustractivas
values = [(1000, 'M'), (900, 'CM'), (500, 'D'), (400, 'CD')]

Problema 3: Dirección de Escaneo Incorrecta

# ❌ Incorrecto - escaneo de izquierda a derecha sin mirar hacia adelante
for char in s:  # Difícil manejar notación sustractiva

# ✅ Correcto - escaneo de derecha a izquierda
for char in reversed(s):  # Fácil comparar con el valor anterior

Aplicaciones del Mundo Real

1. Numeración de Capítulos

def format_chapter(num: int, title: str) -> str:
    return f"Capítulo {int_to_roman(num)}: {title}"

2. Años de Copyright

function copyrightYear(year) {
    return `©${intToRoman(year)}`;
}

3. Numeración de Listas

public String formatListItem(int index, String content) {
    return String.format("%s. %s", intToRoman(index), content);
}

Conclusión

Los algoritmos de conversión de números romanos demuestran el poder del enfoque greedy para problemas con subestructura óptima. Las implementaciones proporcionadas aquí son:

• Eficientes: O(1) para entero a romano, O(n) para romano a entero
• Legibles: Lógica clara que coincide con las reglas matemáticas
• Robustas: Manejan todas las entradas válidas en el rango estándar
• Probadas: Funcionan para todos los números del 1 al 3999

Ya sea que estés preparándote para entrevistas de código, construyendo un generador de documentos, o simplemente curioso sobre algoritmos, estas implementaciones proporcionan una base sólida.

Para una interfaz fácil de usar sin escribir código, prueba nuestro convertidor de números romanos en línea con resultados instantáneos y soporte para notación extendida.

---

¿Quieres aprender más? Explora nuestra guía completa de números romanos o mira cómo usar números romanos en Excel.