Leetcode - Roman to Integer

Ji Kim·2020년 9월 18일
0

Algorithm

목록 보기
21/34

Leetcode : Roman to Integer

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

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1

Input

"III"

Output

3

Example 2

Input

"IV"

Output

4

Example 3

Input

"IX"

Output

9

Example 4

Input

"LVIII"

Output

58
// L = 50, V= 5, III = 3.

Example 5

Input

"MCMXCIV"

Output

1994
//M = 1000, CM = 900, XC = 90 and IV = 4

Approach

Similar to Integer to Roman problem, create a dictionary containing corresponding symbol-value for each integer-value. Check if special cases (i.e - 4, 9, 40, 90, 900) already exist in the dictionary - if so, add the value and skip to the next next index.

Solutions

Solution I (Python)

class Solution(object):
    def romanToInt(self, s):
        result = 0 
        dic = {"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}
        
        if (s in dic):
            return dic[s]
        else:
            i = 0
            
            while(i < len(s)):
                chk = s[i:(i+2)]
                if (chk in dic):
                    result = result + dic[s[i:(i+2)]]
                    i = i + 2
                else:
                    result = result + dic[s[i]]
                    i = i + 1
            
            return result

Result

Runtime: 40 ms
Memory Usage: 12.8 MB
Runtime Beats 78.60% of Python Submission

Solution II (JavaScript)

let romanToInt = function(s) {
    let romObj = {
        'I' : 1,
        'V' : 5,
        'X' : 10,
        'L' : 50,
        'C' : 100,
        'D' : 500,
        'M' : 1000
    }
    
    let number = 0;
    
    for(let i = 0; i < s.length; i++) {
        if(romObj[s[i+1]] > romObj[s[i]]) {
            number = number + romObj[s[i+1]] - romObj[s[i]];
            i++;
        } else {
            number = number + romObj[s[i]]; 
        }
    }
    
    return number; 
    
     
};

Result

Runtime: 144 ms
Memory Usage: 39.8 MB
Runtime Beats 97.77% of JavaScript Submission

profile
if this then that

0개의 댓글