ローマ数字アルゴリズム：Python・JavaScript・Javaによる実装

ローマ数字と整数の相互変換は、コーディング面接・競技プログラミング・実際のアプリケーション開発で頻繁に登場する定番のプログラミング問題です。本ガイドでは、Python・JavaScript・Javaによる最適化された実装と、その背後にあるアルゴリズムの解説を提供します。

問題の理解

解決すべき問題は、相互に関連した2つのサブ問題から成ります。

1. 整数からローマ数字へ： アラビア数字（例：1994）をローマ数字（MCMXCIV）に変換する
2. ローマ数字から整数へ： ローマ数字（例：MCMXCIV）をアラビア数字（1994）に変換する

制約条件

• 入力範囲：1〜3999（標準的なローマ数字の範囲）
• 標準的な減算記法を使用する（IV・IX・XL・XC・CD・CM）
• すべての有効なローマ数字の組み合わせを処理する

貪欲アルゴリズムのアプローチ

いずれの変換にも貪欲アルゴリズムの戦略を用います。

整数からローマ数字へ（貪欲法）

1. 値とローマ数字の対応表を降順で作成する
2. 各「値・数字」ペアに対して：
   • その数字をできるだけ多く使用する
   • 残りの数値からその値を引く
3. 数値がゼロになるまで繰り返す

ローマ数字から整数へ（貪欲法）

1. ローマ数字の文字列を左から右にスキャンする
2. 各記号に対して：
   • 次の記号より小さい場合は減算する（減算記法）
   • そうでない場合は加算する
3. 累積した合計値を返す

Pythonによる実装

整数からローマ数字へ

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:
        # How many times does this value fit?
        count = num // value
        if count:
            result.append(numeral * count)
            num -= value * count

    return ''.join(result)


# Examples
print(int_to_roman(1994))   # MCMXCIV
print(int_to_roman(58))     # LVIII
print(int_to_roman(3999))   # MMMCMXCIX

ローマ数字から整数へ

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 length of string
    Space Complexity: O(1) - fixed size mapping
    """
    # Mapping of Roman numerals to values
    roman_map = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }

    result = 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 (subtractive notation)
        if value < prev_value:
            result -= value
        else:
            result += value

        prev_value = value

    return result


# Examples
print(roman_to_int('MCMXCIV'))  # 1994
print(roman_to_int('LVIII'))    # 58
print(roman_to_int('IX'))       # 9

代替案：左から右へのスキャン

def roman_to_int_v2(s: str) -> int:
    """
    Alternative implementation scanning left to right.
    """
    roman_map = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }

    result = 0

    for i in range(len(s)):
        current = roman_map[s[i]]

        # Look ahead: if next symbol is larger, subtract current
        if i + 1 < len(s) and current < roman_map[s[i + 1]]:
            result -= current
        else:
            result += current

    return result

JavaScriptによる実装

整数からローマ数字へ

/**
 * 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) {
        while (num >= value) {
            result += numeral;
            num -= value;
        }
    }

    return result;
}

// Examples
console.log(intToRoman(1994));  // MCMXCIV
console.log(intToRoman(58));    // LVIII
console.log(intToRoman(3999));  // MMMCMXCIX

ローマ数字から整数へ

/**
 * 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 result = 0;

    for (let i = 0; i < s.length; i++) {
        const current = romanMap[s[i]];
        const next = romanMap[s[i + 1]];

        // If current is less than next, subtract (subtractive notation)
        if (next && current < next) {
            result -= current;
        } else {
            result += current;
        }
    }

    return result;
}

// Examples
console.log(romanToInt('MCMXCIV'));  // 1994
console.log(romanToInt('LVIII'));    // 58
console.log(romanToInt('IX'));       // 9

ES6+版：reduceを使った関数型アプローチ

/**
 * Functional approach using reduce
 */
const romanToIntFunctional = (s) => {
    const map = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };

    return s.split('').reduce((acc, char, i, arr) => {
        const current = map[char];
        const next = map[arr[i + 1]];
        return acc + (next && current < next ? -current : current);
    }, 0);
};

Javaによる実装

整数からローマ数字へ

/**
 * Convert an integer to Roman numerals
 *
 * Time Complexity: O(1)
 * Space Complexity: O(1)
 */
public class RomanConverter {

    public String intToRoman(int num) {
        // Parallel arrays for values and numerals
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] numerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder result = new StringBuilder();

        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                result.append(numerals[i]);
                num -= values[i];
            }
        }

        return result.toString();
    }

    // Examples
    public static void main(String[] args) {
        RomanConverter converter = new RomanConverter();
        System.out.println(converter.intToRoman(1994));  // MCMXCIV
        System.out.println(converter.intToRoman(58));    // LVIII
        System.out.println(converter.intToRoman(3999));  // MMMCMXCIX
    }
}

ローマ数字から整数へ

/**
 * Convert Roman numerals to an integer
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
public class RomanConverter {

    public int romanToInt(String s) {
        // Create mapping
        Map<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 result = 0;
        int prevValue = 0;

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

            // Subtractive notation check
            if (currentValue < prevValue) {
                result -= currentValue;
            } else {
                result += currentValue;
            }

            prevValue = currentValue;
        }

        return result;
    }

    // Examples
    public static void main(String[] args) {
        RomanConverter converter = new RomanConverter();
        System.out.println(converter.romanToInt("MCMXCIV"));  // 1994
        System.out.println(converter.romanToInt("LVIII"));    // 58
        System.out.println(converter.romanToInt("IX"));       // 9
    }
}

アルゴリズムの分析

時間計算量

整数からローマ数字へ：

• O(1) — 定数時間
• 常に13個の「値・数字」ペアを反復処理する
• 入力サイズに依存しない

ローマ数字から整数へ：

• O(n) — 線形時間
• nはローマ数字文字列の長さ
• 各文字を1回ずつ調べる必要がある

空間計算量

いずれのアルゴリズムも：

• O(1) — 定数空間
• 入力に関わらず固定サイズのマッピングを使用
• 結果の文字列・数値のサイズは上限が決まっている

貪欲アルゴリズムが有効な理由

貪欲アルゴリズムがローマ数字に対して有効なのは、以下の性質を持つためです。

1. 最適部分構造： 最適解はサブ問題の最適解を含む
2. 貪欲選択性： 局所的に最適な選択が大域的に最適な解につながる
3. 重複するサブ問題がない： 各値は独立して使用される

重要な直感：常に使用可能な最大値を先に選ぶことで、最も短いローマ数字表現が保証されます。

エッジケースとバリデーション

入力バリデーション

def int_to_roman_safe(num: int) -> str:
    """Integer to Roman with validation"""
    if not isinstance(num, int):
        raise TypeError("Input must be an integer")
    if num < 1 or num > 3999:
        raise ValueError("Input must be between 1 and 3999")

    return int_to_roman(num)


def roman_to_int_safe(s: str) -> int:
    """Roman to Integer with validation"""
    if not isinstance(s, str):
        raise TypeError("Input must be a string")
    if not s:
        raise ValueError("Input cannot be empty")

    # Validate characters
    valid_chars = set('IVXLCDM')
    if not all(c in valid_chars for c in s.upper()):
        raise ValueError("Invalid Roman numeral characters")

    return roman_to_int(s.upper())

テストケース

# Test Integer to Roman
assert int_to_roman(1) == 'I'
assert int_to_roman(4) == 'IV'
assert int_to_roman(9) == 'IX'
assert int_to_roman(58) == 'LVIII'
assert int_to_roman(1994) == 'MCMXCIV'
assert int_to_roman(3999) == 'MMMCMXCIX'

# Test Roman to Integer
assert roman_to_int('I') == 1
assert roman_to_int('IV') == 4
assert roman_to_int('IX') == 9
assert roman_to_int('LVIII') == 58
assert roman_to_int('MCMXCIV') == 1994
assert roman_to_int('MMMCMXCIX') == 3999

# Test round-trip conversion
for num in range(1, 4000):
    assert roman_to_int(int_to_roman(num)) == num

パフォーマンスの最適化

メモ化（繰り返し変換に対して）

from functools import lru_cache

@lru_cache(maxsize=4000)
def int_to_roman_cached(num: int) -> str:
    """Cached version for repeated conversions"""
    return int_to_roman(num)

バッチ変換

def batch_int_to_roman(numbers: list[int]) -> list[str]:
    """Convert multiple numbers efficiently"""
    return [int_to_roman(num) for num in numbers]


def batch_roman_to_int(numerals: list[str]) -> list[int]:
    """Convert multiple Roman numerals efficiently"""
    return [roman_to_int(s) for s in numerals]

よくある面接の質問

LeetCodeの問題

1. Integer to Roman（LeetCode #12）

   • 難易度：中級
   • 上記の貪欲アルゴリズムを使用する

2. Roman to Integer（LeetCode #13）

   • 難易度：初級
   • 左から右、または右から左へのスキャンを使用する

フォローアップの質問

Q：3999より大きい数値はどのように処理しますか？

A：ビンキュラム記法（×1000を表すオーバーライン）を実装します。

def int_to_roman_extended(num: int) -> str:
    """Support numbers up to 3,999,999 using vinculum"""
    if num >= 4000:
        thousands = num // 1000
        remainder = num % 1000
        return f"{int_to_roman(thousands)}̅{int_to_roman(remainder)}"
    return int_to_roman(num)

Q：ローマ数字文字列をどのように検証しますか？

A：無効なパターンを確認します。

def is_valid_roman(s: str) -> bool:
    """Validate Roman numeral string"""
    # Convert and convert back
    try:
        num = roman_to_int(s)
        return int_to_roman(num) == s.upper()
    except:
        return False

実用的な応用例

1. ドキュメント生成

def format_chapter(num: int, title: str) -> str:
    """Format chapter heading with Roman numerals"""
    return f"Chapter {int_to_roman(num)}: {title}"

2. 著作権年号

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

3. リスト番号付け

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

まとめ

ローマ数字変換アルゴリズムは、最適部分構造を持つ問題に対して貪欲アプローチがいかに強力かを示す好例です。本ガイドで紹介した実装は：

• 効率的： 整数からローマ数字へはO(1)、ローマ数字から整数へはO(n)
• 可読性が高い： 数学的なルールに対応した明快なロジック
• 堅牢： 標準範囲内のすべての有効な入力を処理できる
• 検証済み： 1〜3999のすべての数値で動作確認済み

コーディング面接の準備、ドキュメント生成システムの構築、あるいは単純にアルゴリズムへの興味から学ぶ場合でも、これらの実装は確固たる基盤を提供します。

コードを書かずに手軽に試したい方は、拡張記法にも対応したオンライン ローマ数字変換ツールをご利用ください。

---

さらに学びたい方へ： ローマ数字の完全ガイドや、ExcelでのローマX数字の使い方もご覧ください。