O(n)

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

        re = 0

        i = 0
        while i < len(s):
            if i+1 < len(s) and d[s[i+1]] > d[s[i]]:
                re += d[s[i+1]]-d[s[i]]
                i += 2
                continue
            re += d[s[i]]
            i += 1

        return re

def main():
    s = Solution()

    print(s.romanToInt("III")) # 3
    print(s.romanToInt("IV")) # 4
    print(s.romanToInt("IX")) # 9
    print(s.romanToInt("LVIII")) # 58
    print(s.romanToInt("MCMXCIV")) # 1994

if __name__ == '__main__':
    main()