[Leetcode/파이썬] 12. Integer to Roman

Integer to Roman

---

Seven different symbols represent Roman numerals with the following values:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:

• If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
• If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
• Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.

Given an integer, convert it to a Roman numeral.

 

Example 1:

Input: num = 3749

Output: "MMMDCCXLIX"

Explanation:

3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC as 500 (D) + 100 (C) + 100 (C)
  40 = XL as 10 (X) less of 50 (L)
   9 = IX as 1 (I) less of 10 (X)
Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places

Example 2:

Input: num = 58

Output: "LVIII"

Explanation:

50 = L
 8 = VIII

Example 3:

Input: num = 1994

Output: "MCMXCIV"

Explanation:

1000 = M
 900 = CM
  90 = XC
   4 = IV

 

Constraints:

• 1 <= num <= 3999

 

class Solution:
    def intToRoman(self, num: int) -> str:
        int_to_roman = [
            ['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]
        ]

        # 초기값
        cnt = 0
        res = ''

        for roman, inti in reversed(int_to_roman) :
            cnt = num // inti
            res += roman * cnt
            num %= inti
        
        return res

아라비아 숫자를 로마 숫자로 바꾸는 문제이다. 이런 문제를 몇번 풀어보니 바로 일단 배열로 로마자와 아라비아 숫자를 묶어야 겠다고 생각을 했다. zip으로 묶어도 좋을 듯 하고 dict로 묶어도 좋을 듯 하다. 순회를 위해서 2차원 배열로 정렬하여 [0]의 자리에는 로마, [1]의 자리에는 십진수를 넣어두었다. 

초기값으로 cnt와 res를 표기하고 for loop를 돌면서 res에 로마자를 쌓아나갈 것이다. 여기서 중요한 점은 그리디한 선택을 해야한다는 것이다. 만약 num = 3,000 이라면, 정렬 없이 진행하게 될 경우에는 제대로 된 답변을 얻기 어려울 것이다. 

만약 이런 배열이 익숙하지 않다면 문제를 보고 순서에 관계없이 2차원 배열을 모두 작성한 다음, sort() 메소드를 통하여 정렬을 하는 것이 오히려 오류를 줄일 수 있는 더 좋은 방법이라고 생각한다. 

class Solution:
    def intToRoman(self, num: int) -> str:
        int_to_roman = [
            ['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]
        ]

        # 초기값
        cnt = 0
        res = ''

        int_to_roman.sort(key=lambda x:x[1], reverse=True)

        for roman, inti in int_to_roman :
            cnt = num // inti
            res += roman * cnt
            num %= inti
        
        return res

만약 순서대로 작성할 자신이 없다면 이런 식으로 작성을 하여 가장 높은 숫자가 앞에 오도록 유도한 다음 진행해도 좋을 듯 하다. 

추석 연휴가 지나 다시 박차를 가해야 겠다.