LeetCode 솔루션

[Easy - wk1 - Q2] 13. Roman to Integer

Chloe 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.03 14:50

7,480 조회
6 댓글
0 추천
0 비추천
목록 게시글 쓰기

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.

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

#leetcode, #문제풀이, #easy, #amazon, #adobe, #apple, #bloomberg, #facebook, #google, #microsoft, #tiktok, #yahoo, #oracle, #jpmorgan, #tcs, #hash table, #math, #string

익명
작성일 2022.05.03 20:30

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_dic = {'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}
        total = 0
        i = 0
        while i < len(s):
            if i+1 < len(s) and s[i:i+2] in roman_dic:
                total += roman_dic[s[i:i+2]]
                i+=2
            else:
                total += roman_dic[s[i]]
                i+=1
        return total

익명
작성일 2022.05.04 20:19

// Time Complexity: O(n)
// Space Complexity: O(1)
class Solution {
    func romanToInt(_ s: String) -> Int {
        var result = 0
        var jump = false
        let symbols = Array(s)
        for (idx, symbol) in symbols.enumerated() {
            guard !jump else {
                jump = false
                continue
            }
            
            var nextSymbol = "NA"
            if idx+1 < symbols.count {
                nextSymbol = String(symbols[idx + 1])
            }
            
            switch symbol {
            case "I":
                if nextSymbol == "V" {
                    result += 4
                    jump = true
                } else if nextSymbol == "X" {
                    result += 9
                    jump = true
                } else {
                    result += 1
                }
            case "V":
                result += 5
            case "X":
                if nextSymbol == "L" {
                    result += 40
                    jump = true
                } else if nextSymbol == "C" {
                    result += 90
                    jump = true
                } else {
                    result += 10
                }
            case "L":
                result += 50
            case "C":
                if nextSymbol == "D" {
                    result += 400
                    jump = true
                } else if nextSymbol == "M" {
                    result += 900
                    jump = true
                } else {
                    result += 100
                }
            case "D":
                result += 500
            case "M":
                result += 1000
            default:
                break
            }
        }
        return result
    }
}

[code=swift]// Time Complexity: O(n)
// Space Complexity: O(1)
class Solution {
    func romanToInt(_ s: String) -> Int {
        var result = 0
        var jump = false
        let symbols = Array(s)
        for (idx, symbol) in symbols.enumerated() {
            guard !jump else {
                jump = false
                continue
            }
            
            var nextSymbol = "NA"
            if idx+1 < symbols.count {
                nextSymbol = String(symbols[idx + 1])
            }
            
            switch symbol {
            case "I":
                if nextSymbol == "V" {
                    result += 4
                    jump = true
                } else if nextSymbol == "X" {
                    result += 9
                    jump = true
                } else {
                    result += 1
                }
            case "V":
                result += 5
            case "X":
                if nextSymbol == "L" {
                    result += 40
                    jump = true
                } else if nextSymbol == "C" {
                    result += 90
                    jump = true
                } else {
                    result += 10
                }
            case "L":
                result += 50
            case "C":
                if nextSymbol == "D" {
                    result += 400
                    jump = true
                } else if nextSymbol == "M" {
                    result += 900
                    jump = true
                } else {
                    result += 100
                }
            case "D":
                result += 500
            case "M":
                result += 1000
            default:
                break
            }
        }
        return result
    }
}[/code]

익명
작성일 2022.05.05 03:44

class Solution {
    
    private Map<Character, Integer> map = new HashMap<Character, Integer>();
    
    public int romanToInt(String s) {
        initMap();
        
        int resultSum = 0;
        int last = map.get(s.charAt(s.length()-1));
        if(s.length() > 0){
            resultSum = last;    
        }
        
        // if the current value is less than last value, subtract.
        // otherwise, sum up current value
        for(int i=s.length()-2; i>=0; i--){
            int curr = map.get(s.charAt(i));
            if(curr < last){
                resultSum -= curr;
            }else{
                resultSum += curr;
            }
            last = curr;
        }
        
        return resultSum;
    }
    
    private void initMap(){
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
    }
}

익명
작성일 2022.05.07 01:55

Python

Runtime: 66 ms, faster than 50.28% of Python3 online submissions for Roman to Integer.
Memory Usage: 13.8 MB, less than 98.77% of Python3 online submissions for Roman to Integer.

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

익명
작성일 2022.05.11 21:49

table = {
    "": 0,
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
    # special
    "IV": 4,
    "IX": 9,
    "XL": 40,
    "XC": 90,
    "CD": 400,
    "CM": 900,
}

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = len(s)
        if length <= 1:
            return table[s]

        two = s[0:2]
        if two in table:
            return table[two] + self.romanToInt(s[2:])

        one = s[0:1]
        if one in table:
            return table[one] + self.romanToInt(s[1:])
        return 0

익명
작성일 2022.05.12 06:48

var romanToInt = function(s) {
    // first let the computer know the symbols and its meaning.
    
    const symbol = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    let output = 0;
        // if the index el is smaller than index+1 el, then
        // calculate as 1000-100 or 100-10
    for (let i = 0; i < s.length; i++) {
        
        if (symbol[s[i]] < symbol[s[i+1]]) {
            output += (symbol[s[i+1]] - symbol[s[i]]);
            i+=1;
        }
        else {
            output += symbol[s[i]];
        }
    }
    return output;
};