RSSフィードを購読
Python Coding Challenge - How will you convert an integer into a roman numeral?
(Python コーディングチャレンジ [ int 値をローマ数字表記に変換しよう！] 編)
(Python コーディングチャレンジ [ int 値をローマ数字表記に変換しよう！] 編)
プログラム自体はそれほど難しくありませんが、なかなか興味深いでしょ？
問題：
int 値が与えられます。その値をローマ数字で表した文字列を返すプログラムを記述してください。ただし、与えられる int 値は 1 から 3999 までの数値とします。また、作成するローマ字表記文字列は一般的な記法にそって 「大きい桁の数字」から「小さい桁の数字」に並べる decreasing order とします。
ローマ数字は以下の表の７つのアルファベットで表されます:
ローマ数字として用いられる記号
- Wikipedia -
同じ記号は３回まで繰り返される可能性があります。また、最上位の桁の数字が 4 または 9 の場合は、大きな数字の左側に小さな数字を書く「引き算 (減算)」表記を利用するのが一般的です。通常の表記法の場合、この組み合わせは以下の表のとおり６種類存在します:
ローマ数字における減算表記
- Wikipedia -
その他ローマ字表記についてもっと詳しく知りたい方は Wikipedia 等で検索してみてください。
また関数定義は以下のような形です (同じである必要はありません):
def int_to_roman(self, num: int) -> str:
...
...
実装したプログラムは以下のテストをクリアしなければいけません:
import unittest
class TestIntToRoman(unittest.TestCase):
def test_pass_1_return_I(self):
res = int_to_roman(1)
self.assertEqual(res, 'I')
def test_pass_3_return_III(self):
res = int_to_roman(3)
self.assertEqual(res, 'III')
def test_pass_4_return_IV(self):
res = int_to_roman(4)
self.assertEqual(res, 'IV')
def test_pass_5_return_V(self):
res = int_to_roman(5)
self.assertEqual(res, 'V')
def test_pass_6_return_VI(self):
res = int_to_roman(6)
self.assertEqual(res, 'VI')
def test_pass_8_return_VIII(self):
res = int_to_roman(8)
self.assertEqual(res, 'VIII')
def test_pass_9_return_IX(self):
res = int_to_roman(9)
self.assertEqual(res, 'IX')
def test_pass_31_return_XXXI(self):
res = int_to_roman(31)
self.assertEqual(res, 'XXXI')
def test_pass_1960_return_MCMLX(self):
res = int_to_roman(1960)
self.assertEqual(res, 'MCMLX')
def test_pass_3999_return_MMMCMXCIX(self):
res = int_to_roman(3999)
self.assertEqual(res, 'MMMCMXCIX')
if __name__ == '__main__':
unittest.main()
class TestIntToRoman(unittest.TestCase):
def test_pass_1_return_I(self):
res = int_to_roman(1)
self.assertEqual(res, 'I')
def test_pass_3_return_III(self):
res = int_to_roman(3)
self.assertEqual(res, 'III')
def test_pass_4_return_IV(self):
res = int_to_roman(4)
self.assertEqual(res, 'IV')
def test_pass_5_return_V(self):
res = int_to_roman(5)
self.assertEqual(res, 'V')
def test_pass_6_return_VI(self):
res = int_to_roman(6)
self.assertEqual(res, 'VI')
def test_pass_8_return_VIII(self):
res = int_to_roman(8)
self.assertEqual(res, 'VIII')
def test_pass_9_return_IX(self):
res = int_to_roman(9)
self.assertEqual(res, 'IX')
def test_pass_31_return_XXXI(self):
res = int_to_roman(31)
self.assertEqual(res, 'XXXI')
def test_pass_1960_return_MCMLX(self):
res = int_to_roman(1960)
self.assertEqual(res, 'MCMLX')
def test_pass_3999_return_MMMCMXCIX(self):
res = int_to_roman(3999)
self.assertEqual(res, 'MMMCMXCIX')
if __name__ == '__main__':
unittest.main()
考え方:
数字からローマ字への変換用テーブルを作成しておきます。このテーブル (v) は２要素のタプルからなるリストとして定義しますが、１つのタプルは (value[int], symbol[str]) とします。テーブル v に含まれる要素は上の「問題」で掲載した２つの表のすべての要素を含みますが、各要素は value による「降順」に並べておきます。
ローマ字に変換する int 値 num (1 <= num <= 3999) が与えられます。変換テーブル v を要素数分ポインタ i で走査していきます。この時 num // v[i][0] を実行することで、該当する value (== v[i][0]) が含まれる個数を取得することができますから、対応する symbol をその個数分 roman_str 変数にプラスしていくと同時に num から今回変換した分の値を引きます。
この操作を num の値が 0 になるまで繰り返したときに roman_str には答えとなる文字列がセットされている、ということになります。
int値 -> ローマ字表記変換プログラム実装例：
def int_to_roman(num: int) -> str:
v = [
(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_str = ''
for i in range(len(v)):
if num == 0:
break
if d := num // v[i][0]:
roman_str += v[i][1] * d
num -= v[i][0] * d
return roman_str
v = [
(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_str = ''
for i in range(len(v)):
if num == 0:
break
if d := num // v[i][0]:
roman_str += v[i][1] * d
num -= v[i][0] * d
return roman_str
Complexity Analysis
(アルゴリズム解析 - 実行時間解析)
与えられる数値に関わらずループが実行されるのは常に配列 v の要素数分 (== 固定) です。よってこのアルゴリズムの時間計算量 (time complexity) は O(1) です。
次のグラフは、与える int 値を 1 から 3999 まで変化させながらそれぞれの int 値において 100 回の試行を行った場合の実行時間計測グラフです:
「Int 値 -> ローマ字表記変換プログラム」の実行時間計測グラフ