検索ガイド -Search Guide-

単語と単語を空白で区切ることで AND 検索になります。
例: python デコレータ ('python' と 'デコレータ' 両方を含む記事を検索します)
単語の前に '-' を付けることで NOT 検索になります。
例: python -デコレータ ('python' は含むが 'デコレータ' は含まない記事を検索します)
" (ダブルクオート) で語句を囲むことで 完全一致検索になります。
例: "python data" 実装 ('python data' と '実装' 両方を含む記事を検索します。'python data 実装' の検索とは異なります。)
python_coding_challenge

Python coding challenge - int 値をローマ数字表記に変換しよう! 投稿一覧へ戻る

Published 2022年7月20日11:16 by mootaro23

SUPPORT UKRAINE

- Your indifference to the act of cruelty can thrive rogue nations like Russia -

Python Coding Challenge - How will you convert an integer into a roman numeral?
(Python コーディングチャレンジ [ int 値をローマ数字表記に変換しよう!] 編)

プログラム自体はそれほど難しくありませんが、なかなか興味深いでしょ?
問題:
int 値が与えられます。その値をローマ数字で表した文字列を返すプログラムを記述してください。ただし、与えられる int 値は 1 から 3999 までの数値とします。また、作成するローマ字表記文字列は一般的な記法にそって 「大きい桁の数字」から「小さい桁の数字」に並べる decreasing order とします。
ローマ数字は以下の表の7つのアルファベットで表されます:
python_coding_challenge_roman_numerals
ローマ数字として用いられる記号
- Wikipedia -
同じ記号は3回まで繰り返される可能性があります。また、最上位の桁の数字が 4 または 9 の場合は、大きな数字の左側に小さな数字を書く「引き算 (減算)」表記を利用するのが一般的です。通常の表記法の場合、この組み合わせは以下の表のとおり6種類存在します:
python_coding_challenge_roman_negative_notation
ローマ数字における減算表記
- 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()
考え方:
数字からローマ字への変換用テーブルを作成しておきます。このテーブル (v) は2要素のタプルからなるリストとして定義しますが、1つのタプルは (value[int], symbol[str]) とします。テーブル v に含まれる要素は上の「問題」で掲載した2つの表のすべての要素を含みますが、各要素は 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
Complexity Analysis
(アルゴリズム解析 - 実行時間解析)
与えられる数値に関わらずループが実行されるのは常に配列 v の要素数分 (== 固定) です。よってこのアルゴリズムの時間計算量 (time complexity) は O(1) です。
次のグラフは、与える int 値を 1 から 3999 まで変化させながらそれぞれの int 値において 100 回の試行を行った場合の実行時間計測グラフです:
python_coding_challenge_roman_numerals_time_complexity_chart
「Int 値 -> ローマ字表記変換プログラム」の実行時間計測グラフ