[Leetcode/Python] Roman to Integer

Top Interview Questions 의 Easy Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

 

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

 

 

Code:

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

1. 정답을 구할 변수와 로마자와 숫자에 대해 맵핑한 딕셔너리를 생성한다.

2. 매개변수 리스트를 뒤쪽에서부터 탐색한다. 뒤쪽에서 탐색하는 아이디어는 Hint에 쓰여 있어서 시도했다.

3. 2글자씩 확인해서, 조건에 부합하는 숫자가 있으면 romint에서 찾아 answer에 더하고, 두 글자를 처리한 것에 상응하여 i(인덱스)를 2씩 뺀다. 조건에 부합하는 2자리 로마자가 없다면 1자리 로마자로 처리하고 romint에서 찾아 answer에 더한다. 그리고 i(인덱스)를 1씩 뺀다.

4. 탐색할 i가 0일 경우 while문을 빠져나오게 된다. 이전 loop에서 i가 -1이 되어 while문을 빠져나왔다면 문제가 없지만, 0이 되었을 경우 i=1까지만 탐색한 것이기 때문에 i=0도 탐색해야한다. 이를 리턴 시에 함께 처리해준다.