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

โจทย์ปัญหา

แปลงจำนวนเต็มระหว่าง 1 ถึง 3999 เป็น Roman Numerals (เลขโรมัน)

กฎเลขโรมัน

หลักการ: ใช้สัญลักษณ์ที่ใหญ่ที่สุดที่ ≤ เหลืออยู่ ทำซ้ำจนหมด (Greedy Approach)

ตัวอย่าง

Input: 3949
Output: MMMCMXLIX
Breakdown: 3000(MMM) + 900(CM) + 40(XL) + 9(IX)

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

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

void printRoman(int number) {
    int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    string symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    for (int i = 0; i < 13; i++) {
        while (number >= values[i]) {
            cout << symbols[i];
            number -= values[i];
        }
    }
}

int main() {
    int number = 3949;
    printRoman(number);
    cout << endl;

    // Test cases
    vector<int> tests = {1, 4, 9, 58, 1994, 3999};
    for (int n : tests) {
        cout << n << " = ";
        printRoman(n);
        cout << endl;
    }
    return 0;
}

ผลลัพธ์

MMMCMXLIX
1 = I
4 = IV
9 = IX
58 = LVIII
1994 = MCMXCIV
3999 = MMMCMXCIX

Complexity Analysis

• Time: O(1) - Loop คงที่ 13 รอบ, แต่ละรอบวนสูงสุด 3 ครั้ง (M)
• Space: O(1)

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

• ใช้ Greedy Algorithm - เลือกสัญลักษณ์ใหญ่สุดที่เป็นไปได้ทุกขั้นตอน
• จัดการ Subtractive Notation (IV, IX, XL, XC, CD, CM) โดยใส่ใน Array ตั้งแต่แรก
• เลขโรมันมาตรฐานรองรับได้สูงสุด 3999 (MMMCMXCIX) เพราะไม่มีสัญลักษณ์ 5000
• สำหรับเลขใหญ่กว่า ต้องใช้ Overline (×1000) หรือสัญลักษณ์พิเศษ

ฟังก์ชันกลับ (Roman to Integer)

int romanToInt(string s) {
    unordered_map<char, int> val = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
    int result = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i+1 < s.size() && val[s[i]] < val[s[i+1]])
            result -= val[s[i]];
        else
            result += val[s[i]];
    }
    return result;
}