Integer to Roman
ローマ数字には7つの文字があります。M は1000、D は500、C は100、L は50、X は10、V は5、I は1です。文字は大きいものから小さいものへ並び、足し合わせます。そのため、7はVIIです。同じ文字を4回連続して使うことはありません。4、9、40、90、400、900はそれぞれIV、IX、XL、XC、CD、CMと書き、小さい文字をその後にある大きい文字から引きます。小さい文字が先に置かれるのは、この6つの組み合わせだけです。
整数numが与えられたとき、そのローマ数字を返してください。
関数
- numinteger
- 1から3999までの整数
- 戻り値string
- numを表す大文字のローマ数字
制約
1 ≤ num ≤ 3999
例
- 入力
- num = 49
- 出力
- "XLIX"
- 説明
- 49 は 40 + 9 なので、数字は
XLの次にIXです：XLIX。ILは使えません。I が減算に使われるのはIVとIXの場合だけだからです。
- 入力
- num = 2026
- 出力
- "MMXXVI"
- 説明
- 2026には数字の4も9も含まれていないため、組み合わせは必要なく、文字を足し合わせます。1000 + 1000 + 10 + 10 + 5 + 1 は
MMXXVIです。
- 入力
- num = 944
- 出力
- "CMXLIV"
- 説明
- 944は900 + 40 + 4で、それぞれの部分は減算式のペアです。
CM、XL、IVをつなげるとCMXLIVになります。
発展問題
文字列が標準形式のローマ数字かどうかを確認できますか？XLIXは受け入れ、IIII、IL、VXは拒否します。
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
numを位ごとに分解します。3746は3000 + 700 + 40 + 6です。それぞれの部分を個別に書いて、組み合わせることができます。どの部分に減算式のペアが必要ですか？6つのペアは、それ自体で1つの記号として扱います。7つの文字に、
CM= 900、CD= 400、XC= 90、XL= 40、IX= 9、IV= 4を加えると、組み立てに使える値は13個になります。13個の値を大きい順に並べます。それらを順に見ていき、
numが現在の値以上である間、その記号を追加して値を引きます。リストの最後まで進むと、numは0になります。
解説
6つの減算ペアを独自の記号としてアルファベットに加えれば、数値を書くことは両替をするようなものになります。常に、収まる最大の値を選びます。入力は最大でも3999なので、処理量は少なく、一定です。
加算的に書き、それから長い形式を短くしましょう
考え方
最初はペアを無視して、入るだけMを書き、次にDを書き、以下Iまで続けます。944の場合はDCCCCXXXXIIIIとなります。この加算形式が標準形式と異なるのは、桁が4または9のときだけで、その箇所は常に短縮形がある6つの文字列のいずれかです。DCCCCはCM、CCCCはCD、LXXXXはXC、XXXXはXL、VIIIIはIX、そしてIIIIはIVです。
DCCCCをCCCCより先に置き換えます。そうしないと、900がDCDになってしまいます。十の位と一の位でも同じです。加算形式は最大18文字（3999）なので、処理量はO(1)です。2回目のパスといくつかの一時文字列を使います。
アルゴリズム
MからIまでの7つの文字それぞれについて、numがその値以上である間、その文字を追加し、そのたびに値を減算します。DCCCCをCMに置き換え、次にCCCCをCDに置き換えます。LXXXXをXCに置き換え、次にXXXXをXLに置き換えます。VIIIIをIXに置き換え、次にIIIIをIVに置き換えます。- 文字列を返します。
def intToRoman(num):
letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
numeral = ""
for value, letter in letters:
while num >= value:
numeral += letter
num -= value
# Each long form appears at most once; the longer one goes first.
fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
for long_form, short_form in fixes:
numeral = numeral.replace(long_form, short_form)
return numeral13個の値を超える貪欲法
考え方
7つの文字と6つのペアを値の大きい順に並べます: M 1000、CM 900、D 500、CD 400、C 100、XC 90、L 50、XL 40、X 10、IX 9、V 5、IV 4、I 1。収まる最大の値を選ぶのが常に正しい方法です。下の位の値はどれも一つ上の位の最小の値より小さいため、ループは次の位に触れる前に一つの位の処理を終えます。一つの位の中では、9、5、4、1の値を使って各桁を標準的な方法で表します。9は9の記号、5から8は5の記号に最大3つの1の記号を加えたもの、4は4の記号、1から3は1の記号です。
3746の場合、ループは MMM、D、CC、XL、V、Iを書き出します: MMMDCCXLVI。表は13行で、答えは最大15文字なので、処理は1回の走査で O(1) です。
アルゴリズム
- 1000から1までの13個の値を、対応する記号とともにペアも含めて列挙します。
- 空の文字列から始めます。
- 各行について、
numが値以上である間、記号を追加して値を減算します。 - すべての行が完了したら、文字列を返します。
def intToRoman(num):
values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
parts = []
for value, symbol in zip(values, symbols):
while num >= value: # take the largest value that still fits
parts.append(symbol)
num -= value
return "".join(parts)
落とし穴と境界ケース
- 表で
CMの前にDを置くこと。900 はDCDになってしまいます。 - 各行で
whileの代わりにifを使うこと。3000 にはMが3回必要ですが、ifを使うとMCMDCDCXCXになってしまいます。 - ほかのペアを作り出すこと。99 は
ICではなくXCIX、45 はVLではなくXLVです。 - C で、バッファが小さすぎること。最も長い答えである3888は15文字なので、終端のゼロを含めて16バイト必要です。加算形式では19バイト必要です。
よくある質問3
整数からローマ数字への変換の時間計算量は何ですか？
O(1)。入力は最大でも3999なので、貪欲法のループは表の13行を確認し、記号を最大15個追加します。より大きな数が許可され、Mを繰り返して表記される場合、実行時間はnum / 1000に比例して増加します。
値を順にループせずに、整数をローマ数字に変換できますか？
はい。百の位の ""、C、CC、CCC、CD、D、DC、DCC、DCCC、CMのように、各桁について、その数字に対応する文字列の表を用意します。numの各桁を参照し、文字列を結合します。保存する文字列は34個で、これも O(1)です。
なぜ3999が許可される最大の数なのですか？
Mは最も大きい文字であり、同じ文字を4回連続して使うことはできないため、千の位はMMMまでとなり、3999はMMMCMXCIXです。より大きな数は、文字の上に横線を引いて1000倍するなど、追加の記号を使って表しました。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def intToRoman(num):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
num = 49
期待される出力
"XLIX"