leetcode

どーも!

たかぽんです!

今回はLeetCodeのTwo Sunの解説を行っていきます!

また、WriteCodeEverydayの記念すべき1日目です!

筆者は普段業務で使うのはPHPなのですが、このLeetCodeではPython3を使おうと思います!(今後変える可能性はあります...)

一度もPython3を使ったことがなかったので、そもそも構文から学ぶことにはなりそうですが...w

今回はRoman to Integerと言う問題を解きましたので、それについて解説していきます!

毎回このように細かい開設できるかわからないですが...

余裕がある時はできるだけ細かく解説していければなと思います...!

LeetCode Roman to Integer

さて、まずは問題を簡単に解説しておきます。

ローマ数字から通常の数値に変換する...という関数を作れと言う問題です。

内容に関しては以下です。

ローマ数字は以下の7種類のシンボルから成り立っていて...

III なら、 I = 1が三つなので、 1 x 3で3となります。

XXVIIなら、XX + V + IIなので、 10 * 2 + 5 + 2で27になります。

つまり、文字数とそれに対応する数値をかけた数をそれぞれ足せば良さそうですね。

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

ただし、基本は先程のような形で大丈夫なのですが、一部特例があります。

例えば4ですが、IIIIと表すこともあれば、IVと表すこともあるそうです。(筆者はむしろIVの方がよく見ている気がしますね...!)

つまり、IがVやXの前にある場合、それが表すものは 5 - 1 = 4 や、10 - 1 = 9になる...

同様に、XやCがそれよりも大きな数字を表すものより前にきていた場合、同様に40や90, 400や900になる...と言うことですね。

では実際に実装していった流れに合わせてやってみます。

アルゴリズムの考察

まず最初に、基本的な数値の出し方です。

基本的には入力される文字列が"XXVII"のような形の文字列として入力されます。

そのため、文字列を一つづつみていき、その値が先程の表のどの数字かを確認、そして対応する数値を変数に加算...といった形でできそうです。

いったんそこまでやってみると...

class Solution:
    def romanToInt(self, s: str) -> int:
        sum = 0
        for symbol in s:
            if symbol == 'I' :
                sum += 1
            elif symbol == 'V' :
                sum += 5
            elif symbol == 'X' :
                sum += 10
            elif symbol == 'L' :
                sum += 50
            elif symbol == 'C' :
                sum += 100
            elif symbol == 'D' :
                sum += 500
            elif symbol == 'M' :
                sum += 1000
        
        return sum

こんな感じになりました。

最初にクラス定義と関数定義はデフォルトでされているので、内容部分のみ解説します。

今回扱う文字列はsという引数に渡されてきます。

まずはじめに、sumと言う変数を0で用意し、これに回答となる数値を貯めていきましょう。

そして、その後for文で一文字づつみていきます。

以下のように記載すれば"symbol"という変数に"s"という文字列の中から一つづつ抽出できます...!(すごい簡潔にかけて驚きました...!)

for symbol in s:

そして、その後、for文の中でif, elseif (pythonではelifと呼べばいいのかな・・・?)文を使って、その文字の種類によって、sumに加算する値を切り替えて、足していく...といったことを行っています。

あとはそのままsumを返します。

さて、ここまでで基本的なローマ数字は変換できた...と思われますが、先程の例外を考慮できていません。

そのため、IVという入力がきた場合、1+5 = 6と出てしまうのですが、正確には4です。

そこに対応していきましょう。

for文を使って一文字づつみているので、二文字の位置関係を把握していい感じに...と最初考えていたんですが...(前回見た文字を変数に入れて、その文字がIなおかつ、現在見ている文字がVだったら...等)、ちょっと煩雑になりすぎるなぁ...と。

そこで、結局例外のパターンは6パターンで、出現回数に注目して、現在実装している分から引いてあげればいいのでは?と。

例えば..."IV"の場合、本来は4です。

ただ、先程のアルゴリズムだと、IとVで1と5なので、6になります。

と言うことは、IVが出現したらその回数だけ-2してあげれば大丈夫なはずです。

"IX"の場合も本来は11になります。

しかし、これを9とする例外があるので、-2すれば良さそうです。

桁が変わると...

XL(60->40), XC(110->90), CD(600->400), CM(1100->900)となるので、同じ理論でそれぞれ-20,-200すれば良さそうです。

実際に書いたコードは以下で、"s.count('hoge')"で文字列sの中になんどhogeが出現しているのか回数をカウント、一桁と10桁と100桁でそれぞれカウントを合算し、それぞれの数値をsumから減算した結果を返却。

        onesplaced     = s.count('IV') + s.count('IX')
        tensplaced     = s.count('XL') + s.count('XC')
        hundredsplaced = s.count('CD') + s.count('CM')
        
        return sum - onesplaced*2 - tensplaced*20 - hundredsplaced*200

なので、大まかな流れとしては...

  • 基本的な表の通りに計算をする
  • 計算結果から、特定の例外出現回数*(-2, -20, -200)をして、その分を引く
  • 回答を返す

です。

では、最後に僕が提出した際のコードをそのまま貼っておきますので、是非ご参考にしてください。

提出コード

class Solution:
    def romanToInt(self, s: str) -> int:
        sum = 0
        for symbol in s:
            if symbol == 'I' :
                sum += 1
            elif symbol == 'V' :
                sum += 5
            elif symbol == 'X' :
                sum += 10
            elif symbol == 'L' :
                sum += 50
            elif symbol == 'C' :
                sum += 100
            elif symbol == 'D' :
                sum += 500
            elif symbol == 'M' :
                sum += 1000

        onesplaced = s.count('IV') + s.count('IX')
        tensplaced = s.count('XL') + s.count('XC')
        hundredsplaced = s.count('CD') + s.count('CM')
        
        return sum - onesplaced*2 - tensplaced*20 - hundredsplaced*200

おすすめの記事