Study

leetCodeをPythonで解いていく-13 (Roman to Integer)

leetCodeでやった問題を、アウトプットしていきます。

前おき

回答日: 2022.03

とりあえず、https://leetcode.com/discuss/career/449135/How-to-effectively-use-LeetCode-to-prepare-for-interviews の問題リストを解いていこうと思います。

アルゴリズムの勉強はこれからはじめるのですが、まずはeasyなら今でもできるかなと思ってやってみました。

私のプログラミングレベル

プログラミング歴で言えばトータルでは10年ぐらい(?)でしょうか。

社員時代は業務ではほとんど書いたことがなく、プライベートでちょこちょこ書いていた程度です。4年ぐらい前にフリーランスになってからは、Webサービスのバックエンド開発とかやっています。

アルゴリズムやデータ構造は勉強したことがありません。プロコンとかもほとんどやったことなく、数年前にやったPaizaはBレベルまではできて、Aはできないことが多いけど、できるのも少しはある、Sは全然できないといった感じです。

問題

問題 レベル 選択言語
13 Roman to Integer easy Python3

内容: ローマ数字(I, V, X, L, C, D, M)が与えられるるので、数値に変換して出力しなさいという問題。

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

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Input: s = “III”
Output: 3
Explanation: III = 3.

Input: s = “LVIIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.

Input: s = “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

解法

class Solution(object):
    def romanToInt(self, s) -> int:
        """
        :type s: str
        :rtype: int
        """
        ans = 0
        # extract 4x/9x, convert to "--" as dummy character means 0
        for i, v in enumerate(s):
            if i == 0:
                continue
            # 4, 9
            if v == "V" and s[i - 1] == "I":
                ans += 4
                s = s[0:i - 1:] + "--" + s[i + 1::]
            if v == "X" and s[i - 1] == "I":
                ans += 9
                s = s[0:i - 1:] + "--" + s[i + 1::]

            # 40, 90
            if v == "L" and s[i - 1] == "X":
                ans += 40
                s = s[0:i - 1:] + "--" + s[i + 1::]
            if v == "C" and s[i - 1] == "X":
                ans += 90
                s = s[0:i - 1:] + "--" + s[i + 1::]

            # 400, 900
            if v == "D" and s[i - 1] == "C":
                ans += 400
                s = s[0:i - 1:] + "--" + s[i + 1::]
            if v == "M" and s[i - 1] == "C":
                ans += 900
                s = s[0:i - 1:] + "--" + s[i + 1::]

        print(f"remain: {s=} ")
        # add remained value
        roman_int = {
            "-": 0,
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }
        for v in s:
            ans += roman_int[v]

        print(f"{ans=}")
        return ans


if __name__ == '__main__':
    Solution().romanToInt("III")
    Solution().romanToInt("LVIII")
    Solution().romanToInt("MCMXCIV")

結果

とりあえず思いついたのが、 文字列全検索で4x、9xを抜く -> 残りの文字列を全検索 というアプローチでした。でこれをそのまま書きました。

一応、このコードでも通りは、しました。

ただ、forループを2回回していますし、最初のfor文の中でif文を繰り返し使っているので、実行速度が遅いですね・・・ ベスト解法ではなさそうです。

leetCodeは課金しないと正解を見ることはできません。私はまだ課金はしていないので、現時点では正解がわからないのですが、課金したら確認しておこうと思います。

雑感

ちょっと苦労しました。easyでこのレベルかって感じです。先が思いやられそうです。

アルゴリズムの勉強とleetCodeを同時並行ですすめる気ではいますが、最初の内は、アルゴリズムやデータ構造の座学に重点を置くつもりです。