[Leetcode] 12. Integer to Roman_해설, 풀이, 설명

---

안녕하세요, HELLO

 

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

 

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

---

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

 

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

 

STEP 3. 'Integer to Roman' 해설

 

STEP 4. 'Integer to Roman' solution

 

반응형

 

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

 

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 an integer, convert it to a roman numeral.

---

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

예를 들어, 로마자로 2를 II로 쓰고, 이는 1을 두 번 더한 값입니다. 12는 X+II인 XII로 씁니다. 숫자 27은 XXVII로 쓰여 있는데 XX+V+II입니다.

로마자는 보통 왼쪽에서 오른쪽으로 가장 큰 것부터 가장 작은 것까지 씁니다. 그러나 4의 숫자는 IIII가 아닙니다. 대신에 숫자 4는 IV라고 씁니다. 1은 5보다 앞에 있기 때문에 4를 뺍니다. 같은 원리가 9번에도 적용되는데, 이 원리로 IX로 표기됩니다. 뺄셈이 사용되는 여섯 가지 예는 다음과 같습니다.

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

 

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

---

Constraints:

• 1 <= num <= 3999

---

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

 

■ Runtime: 73 ms, faster than 48.31% of Python3 online submissions for Integer to Roman.
■ Memory Usage: 13.8 MB, less than 98.83% of Python3 online submissions for Integer to Roman.

 

class Solution:
    def intToRoman(self, num: int) -> str:
        word = ""
        lst = [["I", 1], ["IV", 4], ['V', 5], ['IX', 9],
               ['X', 10], ['XL', 40], ['L', 50], ['XC', 90],
               ['C', 100], ['CD', 400], ['D', 500], ['CM', 900], ['M', 1000]]
        
        for sym, val in reversed(lst):
            if num // val:
                count = num // val
                word += (sym * count)
                num = num % val
        
        return word

 

---

STEP 3. 'Integer to Roman' 해설

 

코드를 작성하면서 참고한 영상 URL 공유드립니다.

 

URL : https://youtu.be/ohBNdSJyLh8

 

 

STEP 4. 'Integer to Roman' solution

 

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

 

1. Build a hashmap to map each digit number to a symbol
2. Start from the smallest digit, check if the number is either 4 or 9
3. If either 4 or 9, apply the subtraction rule, otherwise the normal rule,
   all based on the num to symbol map
4. Move to the next digit (by dividing 10)

 

■ Runtime: 63 ms, faster than 65.88% of Python3 online submissions for Integer to Roman.
■ Memory Usage: 14 MB, less than 38.97% of Python3 online submissions for Integer to Roman.

 

class Solution:
    def intToRoman(self, num: int) -> str:
        num_to_symbol = {0: "", 1: "I", 5: "V", 10: "X", 50: "L", 100: "C", 500: "D", 1000: "M"}
        result = ""
        m = 1
        while num:
            d = num%10
            if d%5 == 4:
                result = num_to_symbol[m] + num_to_symbol[(d//5+1)*5*m] + result
            else:
                result = num_to_symbol[(d//5)*5*m] + num_to_symbol[m]*(d%5) + result
            num = num//10
            m *= 10
        return result

 

---

■ 마무리

 

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

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

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

감사합니다.