แปลงเลขโรมันเป็นเลขฐานสิบ (1-3999) ใน C++

โจทย์ปัญหา

แปลง Roman Numeral String (1-3999) เป็น Integer

กฎการอ่านเลขโรมัน

• สัญลักษณ์: I=1, V=5, X=10, L=50, C=100, D=500, M=1000
• ปกติ: บวกค่าทั้งหมด (VI = 5+1=6)
• Subtractive Notation: ตัวเล็กหน้าตัวใหญ่ = ลบ (IV = 5-1=4, IX = 10-1=9, XL = 50-10=40, XC = 100-10=90, CD = 500-100=400, CM = 1000-100=900)

ตัวอย่าง

Input: "MCMIV"
Output: 1904
Breakdown: M(1000) + CM(900) + IV(4) = 1904

แนวคิดการแก้ปัญหา

掃描 String จากซ้ายไปขวา:

1. ดูค่าตัวปัจจุบัน (s1) และตัวถัดไป (s2)
2. ถ้า s1 >= s2 → บวก s1
3. ถ้า s1 < s2 → บวก s2 - s1 และข้ามตัวถัดไป (i++)
4. ตัวสุดท้ายเสมอ → บวกค่าตัวนั้น

โค้ดตัวอย่าง (C++)

#include <bits/stdc++.h>
using namespace std;

int romanValue(char r) {
    switch (r) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return -1;
    }
}

int romanToDecimal(string& str) {
    int result = 0;
    for (int i = 0; i < str.length(); i++) {
        int s1 = romanValue(str[i]);
        if (i + 1 < str.length()) {
            int s2 = romanValue(str[i + 1]);
            if (s1 >= s2) {
                result += s1;
            } else {
                result += s2 - s1;
                i++; // Skip next character
            }
        } else {
            result += s1;
        }
    }
    return result;
}

int main() {
    string str = "MCMIV";
    cout << "Integer form: " << romanToDecimal(str) << endl;

    // Test cases
    vector<string> tests = {"III", "IV", "IX", "LVIII", "MCMXCIV", "MMMCMXCIX"};
    for (const string& s : tests) {
        cout << s << " = " << romanToDecimal(const_cast<string&>(s)) << endl;
    }
    return 0;
}

ผลลัพธ์

Integer form: 1904
III = 3
IV = 4
IX = 9
LVIII = 58
MCMXCIV = 1994
MMMCMXCIX = 3999

Complexity Analysis

• Time: O(n) (n = ความยาว String)
• Space: O(1)

คำอธิบายเพิ่มเติม

• อัลกอริทึม Single Pass - อ่านครั้งเดียวจบ
• ใช้ unordered_map แทน Switch ได้สำหรับ Extensibility
• Validation: ควรตรวจสอบ Invalid Roman Numerals (เช่น "IIII", "VX") ถ้าจำเป็น
• ฟังก์ชันคู่: Integer to Roman (Article 1004080907)