LeetCode #13 Roman to Integerをやってみた

問題 (Easy)

Given a roman numeral, convert it to an integer.
→ 詳細

問題を理解する (5分)

ローマ数字のルール

• 各数字に値するシンボルたち
  I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000
• 基本は、左から大きい数字のシンボルを並べる
• しかし、1番左に小さい数字のシンボルが来た場合、その数字を右のシンボルから引いた数になる。
• 1番左に小さい数字のシンボルが来る場合というのは、基本で並べたときに小さい数の同じシンボルが4つ並んでしまう時。

解き方を日本語で組み立てる (10分)

1. 文字を数値に変換し、配列に挿入
2. その配列の隣同士の値の大きさを比較する
3. 今の値の方が小さかったら、前の値を配列に入れる
4. 今の値の方が大きかったら、今の値から前の値を引いて配列に入れる
   → そこでペアなので、インデックスを一つスキップする
5. 最後の値が配列に入っていなかったら挿入する。
6. 配列の中の値を全部足す

考えた解き方をJavaScriptコードで表現する (15分)

私が考えたコード↓

動いたけど、見た目、いかにも効率が悪そう… (= =)

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let num_array = [];
    let before_calculate_numbers = [];

    // 1. 文字を数値に変換
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'I') {
            num_array.push(1);
        } else if (s[i] === 'V') {
            num_array.push(5);
        } else if (s[i] === 'X') {
            num_array.push(10);
        } else if (s[i] === 'L') {
            num_array.push(50);
        } else if (s[i] === 'C') {
            num_array.push(100);
        } else if (s[i] === 'D') {
            num_array.push(500);
        } else if (s[i] === 'M') {
            num_array.push(1000);
        }
    }

    // 2. その配列の隣同士の値の大きさを比較する
    for (let i = 1; i < num_array.length; i++) {
        let previous_num = num_array[i - 1];
        let present_num = num_array[i];

        // 3. 今の値の方が小さかったら、前の値を配列に入れる
        if (previous_num >= present_num) {
            before_calculate_numbers.push(previous_num);
        } else {
        /**  4. 今の値の方が大きかったら、今の値から前の値を引いて配列に入れる
        → そこでペアなので、インデックスを一つスキップする **/
            before_calculate_numbers.push(present_num - previous_num);
            i++; 
        }

        //もし一桁だったら、ループ終わり
        if (num_array.length === 1){
            before_calculate_numbers.push(previous_num);
            break;
        }
        // 5.最後の値が配列に入っていなかったら挿入する。
        if (i === num_array.length - 1) {
            before_calculate_numbers.push(present_num);
        }
    }

    // 4. 配列の中の値を全部足す
    let sum = 0;
    for (const number of before_calculate_numbers) {
        sum += number;
    }

    return sum;
};

2度配列に入れて回してるから効率が悪い…
隣同士の値を比較するタイミングで計算もできないかな

ChatGPTにリファクタリングしてもらった

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    // ローマ数字を対応する整数にマッピング
    const symbolToValue = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };

    let total = 0; // 合計値を初期化

    // 文字列の左から右へループ
    for (let i = 0; i < s.length; i++) {
        const current = symbolToValue[s[i]];     // 現在の文字の値
        const next = symbolToValue[s[i + 1]];     // 次の文字の値（存在する場合）

        // もし次の値が存在して、今の値より大きいなら減算する（例：IV → 5 - 1 = 4）
        if (next && current < next) {
            total -= current;
        } else {
            // そうでなければ通常どおり加算する
            total += current;
        }
    }

    return total; // 最終的な合計値を返す
};

気づき

• オブジェクトを作って、直接文字を参照して値を取得している…！
• 私はなぜかfor文の中で、配列の要素の前の値と今の値を比較するために、indexの初期値を1から始めていた。そのため、最後の要素の比較する値がundefinedになり、どの条件文にも引っ掛からず最後の値が残っているかの条件文を書かないといけなくなった。
• 今の要素と次の要素を比較し、直接比較している。

こんなにシンプルに描けるのに、なんでややこしくしたんだろう…
思いついた一つの方法だけに固執せず、もっといろんな方法を考えてみたい。
エラーが出た時に、それを潰す条件文を足すんではなくて、書いているロジックや条件に原因があるのではないかと既存のコードを見直す必要がある。

ChatGPTにもコードを書かせてみる

解法1: 右から左に処理するパターン

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const romanMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };

    let total = 0;
    let prev = 0;

    // 右から左へ走査
    for (let i = s.length - 1; i >= 0; i--) {
        const current = romanMap[s[i]];

        if (current < prev) {
            // 右側の桁の方が大きいなら減算
            total -= current;
        } else {
            // 通常加算
            total += current;
        }

        prev = current;
    }

    return total;
};

気づき

• 左から右に処理をすると、ペアとなる文字列が出た時にインデックスを飛ばす処理が発生してしまう。しかし右から左に処理すると、1文字ずつみるだけでいい。

解法2：Array.prototype.reduce() を使うパターン

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const romanMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };

    return [...s].reduce((total, char, i, arr) => {
        const current = romanMap[char];
        const next = romanMap[arr[i + 1]];

        if (next > current) {
            return total - current;
        } else {
            return total + current;
        }
    }, 0);
};

気づき

reduce()は配列に対して適用され、結果を蓄積していくメソッドです。

array.reduce((累積値, 現在の値, 現在のインデックス, 元の配列) => {}, 初期値)

• これが使えるようになったら、ループと合計処理を数を1文で済ませられる。

今回

[...s].reduce((total, char, i, arr) => {
        const current = romanMap[char];
        const next = romanMap[arr[i + 1]];

        if (next > current) {
            return total - current;
        } else {
            return total + current;
        }
    }, 0);

• [...s]で、文字列を配列化
• total = 累積値
• char = 現在の値 (ローマ数字)
• i = 現在のインデックス ([...s]の配列のインデックス)
• arr = 元の配列 ([...s] で作った展開後の文字配列の参照)

解法3: 正規表現を使ってペアをマッチさせてから合計する

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const romanMap = {
        'IV': 4, 'IX': 9,
        'XL': 40, 'XC': 90,
        'CD': 400, 'CM': 900,
        'I': 1, 'V': 5, 'X': 10,
        'L': 50, 'C': 100, 'D': 500, 'M': 1000
    };

    const pattern = /IV|IX|XL|XC|CD|CM|I|V|X|L|C|D|M/g;
    const matches = s.match(pattern); // 例: "MCMXCIV" → ["M", "CM", "XC", "IV"]

    return matches.reduce((sum, roman) => sum + romanMap[roman], 0);
};

気づき

これは面白い。この方法は知らなかった。
ローマ数字の正しい並び順を、ペア or 単体で分解する ために match() を使ってる

どれがいいんだ？

解法1の 右から左に処理するパターンが1番いいと思った。
解法2は、reduce関数を知っている人だったらいいけど、知らないと難しい
解法3は、正しくローマ数字を分解できるか不明であることが懸念点。

しかし全ての解法において、"IIV" のような 文法違反のローマ数字も処理してしまう。

左から右に文字列を見ていく解法が、バグが起きやすい理由

1. 減算ペアの処理の後に、インデックスをi++で一つスキップしないといけない
2. 最後の文字が単独で処理されずにスキップされる
3. 最後の要素の値が比較したい左側の要素がundefinedになり、undefinedと比較してしまう。