[3日目]　romanToInteger を解いてみた

はじめに

こんにちは！ききてもです！今日も解いたので、アプローチ方法など参考にしてください。

問題の内容

ローマ数字を数字に変換する問題です。

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

(ex) III=3 IV=4(V-I) 

IがVやXより前にあったら、V-I, X-I
XがLやCより前にあったら、L-X, C-X
CがDやMより前にあったら、D-C, M-C

この法則にしたがって問題を解いていきます！

アプローチ方法

 

1. 1. 左から右へ見ていく方法

一番、オーソドックスな解き方で普通に前からあとの文字と比較していく方法ですね。とてもシンプルな考え方で実装も簡単ですが、足し算か引き算を決定するのに、必ず後ろの文字が必要になってきます。この場合、配列外参照のリスクもあります。

1. 1. 右から左に見ていく方法　O(n) 

この方法だと、左から右の際に挙げられたデメリットを解消してくれます。以下に解き方のステップを書きました。

• current_valueとprev_valueの２つを定義しておく
• 文字列をforで繰り返す際、reversed()メソッドを使用して逆順にする。
• current_valueがprev_valueよりも小さかったら、引き算、大きかったら足し算
• prev_value=current_valueで更新

まとめ

逆順にすることで、参照する数が減ったのでより効率的に実装できました。いろんな場面で応用できそうですね。