【LeetCode】12. Integer to Roman 解答・解説【Python】

問題
1. 原文
2. 内容
方針
1. 前提
2. 実装のイメージ
解答
1. 解答1：
2. 解答2
補足・参考・感想

問題

原文

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

1
2
3
4
5
6
7
8

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

Example 1:

Input: num = 3 Output: "III" Explanation: 3 is represented as 3 ones.

1
2
3

Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

Example 2:

Input: num = 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3.

1
2
3

Input: num = 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 3:

Input: num = 1994 Output: "MCMXCIV" Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

1
2
3

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Constraints:

1 <= num <= 3999

内容

ローマ数字(Roman Numerals)は7つの異なるシンボルで表されます。：I, V, X, L, C, D and Mです。

例えば、2はローマ数字ではIIであり、2つのIをつなげることで記載されます。

12はXIIで、単純にXとIIを繋げて書きます。27はXXVIIと、XX、V、IIを繋げて書きます。

ローマ数字は通常大きい方から小さい方へ、左から右へ向かって書かれます。しかし、4はIIIIではなく、代わりにIVと書かれます。1は5の前なので、5から1を引く形でIVと書かれます。

同じ原則はIXのように9にも当てはまります。

このような引き算を行うパターンが6つのあります。→4,9,40,90,400,900

int型の数字が与えられるので、ローマ数字に変換してください。

※正しくない可能性があります。

方針

前提

・辞書(ハッシュテーブル)を使います。

・今回は1,4,5,9,10,40,50,90,100,400,500,900,1000までの各数字をローマ数字に変換して表します。

・上記の各数字を降順にfor文で処理し、与えられた数字numが上記の各数字より大きい場合にローマ数字に変換しつつ、numからその数字を引きます。

実装のイメージ

・1,4,5,9,10,40,50,90,100,400,500,900,1000をキーに、対応するローマ数字を値として降順に辞書にする。

・for文で上記の各数字について処理を行う

→与えられた数字numが上記の各数字よりも大きい限り処理を行う

→→返り値にローマ数字を加える

→→numから上記の数字を差し引く

解答

解答1：

class Solution:
    def intToRoman(self, num: int) -> str:
        number_hash_table = {
            1:"I",4:"IV",5:"V",9:"IX",
            10:"X",40:"XL",50:"L",90:"XC",
            100:"C",400:"CD",500:"D",900:"CM",
            1000:"M"
        }

        ans = ""
        number_list = list(number_hash_table.keys()) #各数字をリストに変換
        for i in number_list[::-1]: #number_list[::-1]は[1000,900,500,400,100,90,50,40,10,9,5,4,1]
            while num >= i: #numがiよりも大きい限り繰り返す
                ans += number_hash_table[i] #ansにnumber_hash_tableの値を結合する。
                num -= i #numからiを引く　→num=3431なら2431,1431,431,31,21,11,1,0と変化していく
                #print(ans,num)
        return ans

class Solution:

def intToRoman(self, num: int) -> str:

number_hash_table = {

1:"I",4:"IV",5:"V",9:"IX",

10:"X",40:"XL",50:"L",90:"XC",

100:"C",400:"CD",500:"D",900:"CM",

1000:"M"

}

ans = ""

number_list = list(number_hash_table.keys()) #各数字をリストに変換

for i in number_list[::-1]: #number_list[::-1]は[1000,900,500,400,100,90,50,40,10,9,5,4,1]

while num >= i: #numがiよりも大きい限り繰り返す

ans += number_hash_table[i] #ansにnumber_hash_tableの値を結合する。

num -= i #numからiを引く　→num=3431なら2431,1431,431,31,21,11,1,0と変化していく

#print(ans,num)

return ans

解答2

class Solution:
    def intToRoman(self, num: int) -> str:
        #大きい数字から記載すると後が楽。
        number_hash_table = {
            1000:"M",
            900:"CM",500:"D",400:"CD",100:"C",
            90:"XC",50:"L",40:"XL",10:"X",
            9:"IX",5:"V",4:"IV",1:"I",
        }
        
        roman_symbol = ""
　　　　#keyはアラビア数字、valueはローマ数字。辞書から同時に取り出して繰り返し処理を行う
        for key,value in number_hash_table.items():
            #number_hash_talbe内の各数字よりも大きい場合、
            #roman数字をroman_symbolに追加して、numからその数(integer)を引く
            while num >= key:
                roman_symbol += value
                num -= key
        return roman_symbol

class Solution:

def intToRoman(self, num: int) -> str:

#大きい数字から記載すると後が楽。

number_hash_table = {

1000:"M",

900:"CM",500:"D",400:"CD",100:"C",

90:"XC",50:"L",40:"XL",10:"X",

9:"IX",5:"V",4:"IV",1:"I",

}

roman_symbol = ""

　　　　#keyはアラビア数字、valueはローマ数字。辞書から同時に取り出して繰り返し処理を行う

for key,value in number_hash_table.items():

#number_hash_talbe内の各数字よりも大きい場合、

#roman数字をroman_symbolに追加して、numからその数(integer)を引く

while num >= key:

roman_symbol += value

num -= key

return roman_symbol

補足・参考・感想

参考

前：3. Longest Substring Without Repeating Characters

次：5. Longest Palindromic Substring

LeetCode 解答・解説記事一覧