[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].

---

문제 풀이

문제 접근

1. 문장의 최대 길이는 15이기 때문에 시간 제한을 고민 하는 것은 의미가 없어 보인다.

풀이

1. 모든 문자에 대해 다 확인해보는 것도 방법이다.
2. 하지만, 소스 코드를 줄이는 방법을 생각해 보자.
3. Roman 숫자의 규칙상 왼쪽에서부터 큰 숫자가 적히고 오른쪽으로 갈 수록 작은 숫자가 적힌다.
4. 만일 왼쪽에서 오른쪽으로 확인을 할때 왼쪽에 작은 숫자가 있다면 그 숫자는 두자리 로만 숫자이다.
5. 예시: IV 는 1, 5 이기 때문에 규칙상 각각 의 숫자로 존재 불가하다. 
   반대로 VI 는 5, 1 이기 때문에 존재할 수 있다. 
6. 즉, 왼쪽부터 확인하면서 뒤에 숫자가 크다면 큰 숫자에서 작은 숫자를 빼주고 더 해주면 된다. 
7. 예시: "LIV" -> 50, 1, 5.
   L > I < V, 50 + (5 - 1) 

소스 코드

class Solution:
    def romanToInt(self, s: str) -> int:
        symbols = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        ans = 0
        index = 0
        n = len(s)
        while index < n:
            if index + 1 < n and symbols[s[index]] < symbols[s[index + 1]]:
                ans += symbols[s[index + 1]] - symbols[s[index]]
                index += 2
            else:
                ans += symbols[s[index]]
                index += 1
        return ans