13 Roman to Integer

1. Description

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

 

Constraints:

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

2. Algorithms

iteration	string	curr	prev	ans	ex) "MCMXCIV"
1	M	1000	0	1000
2	C	100	1000	1100
3	M	1000	100	2100 - 200 = 1900
4	X	10	1000	1910
5	C	100	10	2010 - 20 = 1990
6	I	1	100	1991
7	V	5	1	1996 - 2 = 1994

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_numerals = {'I' : 1, 'V' : 5, 'X' : 10, 'L' : 50, 'C' : 100, 'D' : 500, 'M' : 1000}   
        prev = 0
        curr = 0
        ans = 0
        
        for string in s :
            curr = roman_numerals[string]
            ans += curr
            
            if prev < curr : 
                ans = ans - 2 * prev
                
            prev = curr 
        
        return ans

1. 이전의 라틴어의 숫자를 저장할 prev, 현재 라틴어의 숫자를 저장할 curr, 기본적인 라틴어를 저장하고 있는 roman_numerals dictionary를 생성한다.
2. 각 문자에 대해 먼저 현재 값을 더하고 이전 라틴어의 수가 현재 라틴어의 수보다 작다면 두배 만큼 빼 결국에 이전 값은 -prev를 업데이트 하도록 구성한다
3. 마지막으로 curr의 값을 prev로 업데이트해서 다음 curr과 비교할 수 있도록 업데이트 한다.

과거 값과 현재 값을 업데이트하는 방식이 연속된 자료를 비교할 때 유용한 것 같다.(02 Add Two Numbers의 overflow)

iteration	cursor	value	ex) "MCMXCIV"
1	1	1000
2	3	1900
3	5	1990
4	7	1994

class Solution:
    def romanToInt(self, s: str) -> int:
        
        roman2value={'M':1000,'CM':900,'D':500,'CD':400,'C':100,'XC':90,'L':50,'XL':40,'X':10,'IX':9,'V':5,'IV':4,'I':1}
            
        value=0
        temp=''
        cursor=0
        while cursor<len(s):
            if (cursor+1)!=len(s) and s[cursor]+s[cursor+1] in roman2value:  # Check current character and next character
                value+=roman2value[s[cursor]+s[cursor+1]]
                cursor+=2
            else:
                value+=roman2value[s[cursor]]
                cursor+=1
        return value

1. 모든 경우의 roman numerial case를 dictionary에 저장한다.
2. while문을 사용해 cursor의 길이가 2개 1개인 경우로 나누어 dictionary에 해당 라틴어가 있으면 값을 더하고 커서를 해당 길이만큼 증가시킨다.

3. Conclusion

• Code 1's Time Complexity : $O(N)$
• Code 2's Time Complexity : $O(N)$