[LeetCode] 13. Roman to Integer

13. Roman to Integer

Easy

 

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 ones 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.

 

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

 

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글자의 심볼도 숫자로 지정하고 있다. 
• 앞에 온 심볼이 다음 심볼보다 작은 숫자를 가지면 그것을 처리해줘도 되지만, 딕셔너리에 두글자 심볼도 모두 저장하여 풀수있다.
• 시간복잡도는 마찬가지로 O(N)이 걸린다. 
• 2개씩 문자를 모두 확인한다고 해도 O(2N)이 걸리기 때문에 속도면에서 조금차이날 뿐이지만 그렇게 큰차이는 아니다.
• for문을 사용하지 않는데, 이유는 인덱스를 옮기면서 값을 확인해야하기 때문이다.
• 0부터 인덱스를 탐색할때 s[i:i+2]로 지금 위치에서 2자리 단어를 확인한다.
• 만약 그 단어가 해쉬 테이블에 있다면 그 key에 해당하는 value를 답에 더해준다.
• 그리고 인덱스를 2칸 옮긴다.
• 두자리 단어가 없다면 해당 위치의 한 글자에 해당하는 value를 찾아 더해준다.
• 한 글자에 해당하는 값을 찾았을때는 인덱스를 1증가 시킨다. 
• 인덱스가 문장의 갯수보다 작을때까지만 포인터를 옮기면서 탐색하고 정답을 구한다. 

소스 코드

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