ゼロから始めるLeetCode Day74 「12. Integer to Roman」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day73 「1491. Average Salary Excluding the Minimum and Maximum Salary」

次回
ゼロから始めるLeetCode Day75 「15. 3Sum」

Twitterやってます。

問題

12. Integer to Roman
難易度はMedium。

なんかBadの方が多いので嫌な予感がしてました・・・

ローマ数字は7つの異なる記号で表されます。I、V、X、L、C、D、Mの7つの異なる記号で表されます。
この問題では、以下のように変換されています。

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

例えば、2はローマ数字でIIと書かれていますが、これは単に2つの1を足しただけです。12はXIIと書かれていますが、これは単にX + IIです。二十七という数字は、XXVIIと書かれていますが、これはXX + V + IIです。

ローマ数字は通常、左から右に大きい方から小さい方へと書かれています。しかし、4という数字はIIIIではありません。その代わり、4という数字はIVと書かれています。1は5の前にあるので、それを引くと4になります。9という数字も同じ原理で、IXと書かれています。引き算を使う例は6つあります。

I は V (5) と X (10) の前に置くと 4 と 9 になります。
X は L (50) と C (100) の前に置くと 40 と 90 になります。
C を D (500) と M (1000) の前に置くと 400 と 900 になります。

整数が与えられた時に以上の法則に則ってローマ数字に変換するアルゴリズムを設計してください、という問題です。

なお、入力は1から3999までの範囲内であることが確定しています。

Example 1:
Input: 3
Output: “III”

Example 2:
Input: 4
Output: “IV”

Example 3:
Input: 9
Output: “IX”

Example 4:
Input: 58
Output: “LVIII”
Explanation: L = 50, V = 5, III = 3.

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

解法

class Solution:
    def intToRoman(self, num: int) -> str:
        nums = (1000,900,500,400,100,90,50,40,10,9,5,4,1)
        roman = ("M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I")
        ans = ""
        while num != 0:
            for i, j in enumerate(nums):
                if num >= j:
                    num -= j
                    ans += roman[i]
                    break
        return ans
# Runtime: 52 ms, faster than 60.03% of Python3 online submissions for Integer to Roman.
# Memory Usage: 13.9 MB, less than 33.48% of Python3 online submissions for Integer to Roman.

numsromanでそれぞれの値を保持しておき、0になるまでfor文を回し、その中で値がj以上の場合にのみj分減らし、romanのインデックスをansに加える、というものです。

numsromanの値が一致しているのでインデックスをそのまま使いまわせる、という訳ですね。
今思えば辞書を使った方がスッキリかけそうな気がしないでもないですね。

なお、discussの中には力技で以下のような回答をしていらっしゃる方もいます。

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        result = []
        if num>=1000:
            times = num/1000
            result.append(times*'M')
            num = num%1000
        if num>=900:
            result.append('CM')
            num -=900
        if num>=500 and num<900:
            result.append('D')
            num -= 500
        if num>=400 and num<500:
            result.append('CD')
            num-=400
        if num >=100 and num<400:
            times = num/100
            result.append(times *'C')
            num = num%100
        if num >=90 and num<100:
            result.append('XC')
            num-=90
        if num >=50 and num<90:
            result.append('L')
            num-=50
        if num>=40 and num<50:
            result.append('XL')
            num-=40
        if num>=10 and num<40:
            times = num/10
            result.append(times*'X')
            num %= 10
        if num==9:
            result.append('IX')
            num-=9
        if num>=5 and num<9:
            result.append('V')
            num-=5
        if num==4:
            result.append('IV')
            num-=4
        if num>=1 and num<=3:
            result.append(num*'I')
            num-=num
        return ''.join(result)        
# Runtime: 20 ms, faster than 99.65% of Python online submissions for Integer to Roman.
# Memory Usage: 12.7 MB, less than 65.50% of Python online submissions for Integer to Roman.

https://leetcode.com/problems/integer-to-roman/discuss/715614/Clean-easy-and-fast-Python-Solution

Python3ではなくPythonでの提出です。

解いてみて何となくBadの数が多い理由が分かったような気がします・・・

では今回はここまで。お疲れ様でした。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話

自作のChrome Extensionをインポートした時に "Invalid value for 'content_scripts[0].matches[0]': Empty path."というエラーが出たので解決した