Chương trình chuyển số La Mã sang số nguyên trong Python

Chuyển đổi chuỗi số La Mã (Roman numeral) sang số nguyên. Quy tắc: các ký tự từ trái sang phải giá trị giảm dần, trừ trường hợp trừ (ký tự nhỏ hơn đứng trước ký tự lớn hơn).

Bảng giá trị

Ví dụ

"MCLXVI" = 1000 + 100 + 50 + 10 + 5 + 1 = 1166

"IV" = 5 - 1 = 4; "IX" = 10 - 1 = 9

Thuật toán

1. Tạo dictionary ánh xạ ký tự → giá trị.
2. Duyệt chuỗi từ trái sang phải:
   • Nếu ký tự hiện tại < ký tự tiếp theo: trừ giá trị hiện tại.
   • Ngược lại: cộng giá trị hiện tại.
3. Trả về tổng.

Triển khai Python

class Solution:
    def solve(self, numeral):
        values = {"M": 1000, "D": 500, "C": 100, "L": 50, "X": 10, "V": 5, "I": 1}
        ans = 0
        n = len(numeral)
        for i, ch in enumerate(numeral):
            if i < n - 1 and values[ch] < values[numeral[i + 1]]:
                ans -= values[ch]
            else:
                ans += values[ch]
        return ans

# Test
ob = Solution()
print(ob.solve("MCLXVI"))   # 1166
print(ob.solve("IV"))       # 4
print(ob.solve("MCMXCIV"))  # 1994

Độ phức tạp

• Thời gian: O(n) với n độ dài chuỗi.
• Không gian: O(1).