概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day73 「1491. Average Salary Excluding the Minimum and Maximum Salary」
今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！
問題
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と書かれています。引き算を使う例は６つあります。
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.
numsとromanでそれぞれの値を保持しておき、0になるまでfor文を回し、その中で値がj以上の場合にのみj分減らし、romanのインデックスをansに加える、というものです。
numsとromanの値が一致しているのでインデックスをそのまま使いまわせる、という訳ですね。
今思えば辞書を使った方がスッキリかけそうな気がしないでもないですね。
なお、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.
Python3ではなくPythonでの提出です。
解いてみて何となくBadの数が多い理由が分かったような気がします・・・
では今回はここまで。お疲れ様でした。