[Leetcode] 13. Roman to Integer_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '13. Roman to Integer'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Roman to Integer' 알고리즘 문제

 

STEP 2. 'Roman to Integer' 코드(code)

 

STEP 3. 'Roman to Integer' 해설

 

STEP 4. 'Roman to Integer' solution

 

반응형

 

STEP 1. 'Roman to Integer' 알고리즘 문제

 

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

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.

---

로마자는 7개의 각기 다른 기호 I, V, X, L, C, D와 M로 표시됩니다.

예를 들어, 로마자로 2를 II로 쓰며, 12는 X+II인 XII로 씁니다. 숫자 27은 XXVII로 씁니다.

로마자는 왼쪽에서 오른쪽으로 가장 큰 것부터 가장 작은 것까지 씁니다. 이때, 4는 로마자로 IIII로 쓰지 않습니다. 대신에 숫자 4는 IV라고 쓰며, 1은 5보다 앞에 있기 때문에 5에서 1을 빼서, 4로 표기합니다. 같은 원리가 9에도 적용되는데, 이에 따라 9를 IX로 표기합니다. 뺄셈이 사용되는 여섯 가지 예는 다음과 같습니다.

1. II는 V(5)와 X(10) 앞에 놓이면 4와 9가 됩니다.
2. X를 L(50)과 C(100) 앞에 놓으면 40과 90이 됩니다.
3. C를 D(500)와 M(1000) 앞에 놓으면 400과 900이 됩니다.

 

로마자가 주어지면 정수로 변환합니다.

---

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

---

STEP 2. 'Roman to Integer' 코드(code)

 

■ Runtime: 46 ms, faster than 91.62% of Python3 online submissions for Roman to Integer.
■ Memory Usage: 13.9 MB, less than 80.72% of Python3 online submissions forRoman to Integer.

 

class Solution:
    def romanToInt(self, s: str) -> int:
        lst = {"I": 1, "V" : 5, "X":10, "L":50, "C":100, "D":500, "M":1000}
        
        i = 0
        word = 0

        # one letter
        if len(s) <= 1:
            word = lst[s]

        # two letters
        elif len(s) == 2:
            if lst[s[i]] >= lst[s[i+1]]:
                word = lst[s[i]] + lst[s[i+1]]
            else:
                word = lst[s[i+1]] - lst[s[i]]

        # more than 3 letters
        else:
            while i < len(s) - 1 :
                if lst[s[i]] >= lst[s[i+1]]:
                    word += lst[s[i]]
                    i += 1
                else:
                    word += lst[s[i+1]] - lst[s[i]]
                    i += 2

            # sum last word
            if lst[s[-2]] >= lst[s[-1]]:
                word += lst[s[-1]]
            else:
                pass
        
        return word

---

STEP 3. 'Roman to Integer' 해설

 

단어별로 개수를 확인하여, n번째 숫자와 n+1번째 숫자의 비교를 통해 n번째 숫자가 크면 n번째 숫자를 그대로 반환하고, 작은 경우에는 n+1번째 숫자에서 n번째 숫자를 뺀 연산을 반환했습니다. 

 

그리고 len(s) - 1번째까지 연산이 진행되기에, 마지막 숫자를 검토하였습니다.

 

 

STEP 4. 'Roman to Integer' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

이때, 4를 곱해주는 이유는 로마자는 5배수로 표기하기에 나머지 개념으로 적용한 것입니다.

 

■ Runtime: 41 ms, faster than 96.10% of Python3 online submissions for Roman to Integer.

■ Memory Usage: 13.8 MB, less than 78.57% of Python3 online submissions for Roman to Integer

 

class Solution(object):
    def romanToInt(self, s):
        eq = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
        Output = 0

        for i in s[::-1]:
            if 4 * eq[i] > Output:
                Output += eq[i]
            else:
                Output -= eq[i]

        return Output

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '13. Roman to Integer'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.